P4587 [FJOI2016]神秘数

题目大意：

给出一个正整数序列 \(a\)，每次询问用序列上的一段区间中的数不能通过加和得到的最小的数。

解法：

要求不能得到的最小的数，那么证明比这个数小的都能组成，不然这个数就不是最小的不能组成的数，然后我们考虑如何用一段区间里的数求出这段从一开始连续的区间。

先让这段区间里的数从小到大排序，假设我们当前枚举到第 \(i\) 个数对答案的影响，那么如果在第 i 个之前，能拼出 \(1-a_{i} -1\) 中所有的数，那么就让 \(a_i\) 统计到答案中去，如果当某一时刻的 \(a_i\) 的值比当前能够拼出的最大答案要大，那么答案就是当前能够拼出的最大值加一。

考虑如何对这个区间进行排序，可以主席树进行维护，对这个数列建一棵可持久化权值线段树，于是问题就变成了在这个区间里，每次求第 \(i\) 大的值，判断在此之前是否可以凑出比当前值小的所有值，如果可以，继续累加，否则就输出答案。

可以使用主席数的理由：因为主席树的思想类似于前缀和，但是前缀和维护的是一个数列的值的和，
而主席树还维护了每个值的个数，这样子我们就能通过左右区间分别代表的那棵权值线段树上的每个节点进行求差，
从而得出这段区间里的值在当前节点的覆盖范围中的个数，就可以得到这个区间里第 i 大的数。

Code：

#include <iostream>
#include <cstdio>
using namespace std ;

const int A = 1e9 ;
int n , m , cnt ;
int t[3200005] , ls[3200005] , rs[3200005] , s[3200005] , sum[3200005] ;

int insert ( int pre , int l , int r , int x )
{
	int rt = ++ cnt ;
	ls [ rt ] = ls [ pre ] ;
	rs [ rt ] = rs [ pre ] ;
	s [ rt ] = s [ pre ] + 1 ;
	sum [ rt ] = sum [ pre ] + x ;
	if ( l == r )
		return rt ;
	int mid = ( l + r ) >> 1 ;
	if ( mid >= x )
		ls [ rt ] = insert ( ls [ pre ] , l , mid , x ) ;
	else
		rs [ rt ] = insert ( rs [ pre ] , mid + 1 , r , x ) ;
	return rt ;
}

int query ( int u , int v , int l , int r , int x , int y )
{
	int p = s [ v ] - s [ u ] , q = sum [ v ] - sum [ u ] ;
	if ( x <= l && r <= y )
		return q ;
	if ( !p )
		return 0 ;
	int mid = ( l + r ) >> 1 , res = 0 ;
	if ( mid >= x )
		res = query ( ls [ u ] , ls [ v ] , l , mid , x , y ) ;
	if ( mid < y )
		res += query ( rs [ u ] , rs [ v ] , mid + 1 , r , x , y ) ;
	return res ;
}

int main ( )
{
	cin >> n ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		int x ; cin >> x ;
		t [ i ] = insert ( t [ i - 1 ] , 1 , A , x ) ;
	}
	cin >> m ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		int x , y , be = 0 , qs = 0 ;
		cin >> x >> y ;
		while ( 1 )
		{
			int res = query ( t [ x - 1 ] , t [ y ] , 1 , A , be + 1 , qs + 1 ) ;
			if ( res )
			{
				be = qs + 1 ;
				qs += res ;
			}
			else
				break ;
		}
		cout << qs + 1 << endl ;
	}
	return 0 ;
}