[第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明）]M.Stone Games（主席树）

题目链接：M-Stone Games_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） (nowcoder.com)

Problem

给定一个正整数组成的数组，每次询问一个区间[l, r]内不能组成的最小的正整数。

区间内的数字最多被用一次，可以一个都不选（结果为0）。

比如对于题目样例的数组：\(\{ 1 4 2 1 6 \}\)，询问区间\([3, 5]\)也就是\(\{ 2, 1, 6 \}\)这三个数，他们可以组成的数字有\(\{ 0, 1, 2, 3, 6, 7, 8, 9\}\)，最小的不能表示的就是\(4\)，类比\(mex\)运算。

Analyse

询问特别多，所以每一次的回答复杂度应该要控制到\(O(1) ~ O(log)\)的范围比较好，这给了我们一个方向。

现在来思考，如果区间为空的话，只能组成数字\(0\)，所以答案是\(1\)，尽管“区间为空”这种情况是不会出现的，但是我们可以作为一个思考的起点。

现在给区间里加上\(k\)个\(1\)，不难发现答案（最小的无法表示的数字）是\(k + 1\)。现在来思考，如果这时候加上一个\(x, x > k + 1\)，答案是不变的，如果加上一个\(y, y \le k + 1\)，那么答案将会变为\(k + y\)，注意此时\(k\)发生了改变，可能使得某些区间内的数字原本是\(> k + 1\)的现在变为\(\le k + 1\)的了，所以还要继续检查，直至\(k\)不发生变化。

前面是一个个给区间里面加数字，现在回到这道题的题意，给定一个固定的区间。其实和前面的分析差不多，定义\(k\)：当前状态下，能够从0开始连续表示的最大的数字。

我们先初始\(k\)为\(0\)，然后再找出区间\([l, r]\)内，值\(\le k + 1\)的数字之和记作\(sum\)，且令\(k = sum\)，此时\(k\)发生了改变，可能使得某些数字进入了\([0, k + 1]\)的区间，所以再找一次\(sum\)，令\(k = sum\)，如此循环直至找出的\(sum = k\)，说明答案已经稳定了。

最终的答案\(ans = k+1\)，根据定义不难得出。

现在的问题变为，如何维护“区间内值在[0, k + 1]的范围的数字之和”，这个可以用可持久化线段树（主席树）来维护。

Code

//M.Stone Games
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9, inf = 8e18;
int root[maxn], idx = 0, N, M, a[maxn];
struct Node{int ls, rs, v;}t[maxn * 25];//一般开N*logN空间
vector<int> v;//离散化数组

int getidx(int x){return lower_bound(v.begin(), v.end(), x) - v.begin();}

void insert(int &o, int pre, int x, int s = 0,int e = v.size() - 1)
{
    if(x < s || e < x)return;//递归出口，如果当前区间[s, e]和x无关就跳出 
    o = ++ idx;//分配一个节点给o，这个o引用类型会传给上一个点的ls或者rs 
    t[o] = t[pre];//将信息完全复制 
    t[o].v += v[x];//表示在这个节点下的区间中，多了x
    if(s == e)return;//到叶子节点就跳出 
    int mid = (s + e) / 2;//递归处理左右子树 
    insert(t[o].ls, t[pre].ls, x, s, mid);
    insert(t[o].rs, t[pre].rs, x,mid+1,e);
}

int query_sum(int ln,int rn,int k,int s = 0,int e = v.size() - 1)
{
    if(e <= k)return t[rn].v - t[ln].v;
	if(s > k)return 0; 
	int mid = (s + e) >> 1;
	int s1 = query_sum(t[ln].ls, t[rn].ls, k, s, mid);
	int s2 = query_sum(t[ln].rs, t[rn].rs, k, mid + 1, e);
	return s1 + s2;
}

signed main()
{
	int n, q;scanf("%lld %lld", &n, &q);
	for(int i = 1;i <= n; ++ i)
	{
		scanf("%lld", a + i);
    	v.push_back(a[i]);
    }
    v.push_back(-inf), v.push_back(inf);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    for(int i = 1;i <= n; ++ i)insert(root[i], root[i - 1], getidx(a[i]));
    int ans = 0;
    while(q --)
    {
    	int l, r;scanf("%lld %lld", &l, &r);
    	
    	l = (l + ans) % n + 1, r = (r + ans) % n + 1;
    	if(l > r)swap(l, r);


    	int k = 0;
    	while(true)
    	{
    		int sum = query_sum(root[l - 1], root[r], upper_bound(v.begin(), v.end(), k + 1) - v.begin() - 1);
    		if(k == sum)break;
    		k = sum;
    	}
    	ans = k + 1;
    	printf("%lld\n", ans);
    }
    
	return 0;
}