题目大意：
给你n个数字，m个询问，每次询问[l,r]
求[l,r]这个区间内的数不能够构成的最小正整数（下文称其为区间Mex（并不是严格的区间Mex））
题目思路：
我们逐步解决这个问题
Q1：
如何计算一个区间的MEX ？
假设当前区间[L,R]能够表示的数是[1,x]此时mex = x+1
然后我们扩展这个区间，也就是扩展到a[R+1]这个数字，区间Mex如何变化？
如果a[R+1]>x+1，那么无论如何都无法构成x+1这个数字，那么此时能够表示的数还是[1,x]，区间Mex还是x+1
如果a[R+1]<=x+1，把原本能够构成的每个数字也就是[1,x]全部加这个数字a[R+1],所得集合取并集，得到新的能够表示的数的区间[1,x+a[R+1]]，区间Mex变为x+a[R+1]+1;
重复上述操作，可以一直扩展
Q2----001:时间复杂度的考虑：
如果对于每次询问l，r，我们都暴力从l扩展到r，那么复杂度为O(q*n），显然这里需要一种更为优秀的算法
我们再仔细观察Q1中的扩展操作
如果这个区间内的数字是从小到大排好序的，那么每次扩展的时候，我们查询区间内的小于等于x+1的所有的值的和，记为sum，因为sum是可以扩展上的，所以扩展区间能够表示的数字为[1,x+sum],那么Mex也被扩大到了x+sum+1，那么我们再次查询区间内小于等于Mex的数字，这个时候，肯定多出来了一部分数字，记为up。
那么下次被扩扩展的肯定就是up这一部分数字，如果x+sum+up<Mex,那么此时Mex就是答案来，否则，继续重复上述操作扩展
而这样的扩展操作复杂度为O(log(max[a[i]]]))
Q2-002(另一种扩展的方式/理解）
这里的up表示区间能够表示的最大的数字
x为对于区间当前能够表示的区间的内的数字和
[1,up] --- x
能够扩展的情况： x<=up+1 [1,up+x]
对于区间[L,R]
假设Mex=1
也就是区间[0,0] == [1,up]
待插入的数是[L,R]中小于等于up+1的数字 假设值为sum
如果sum<=up+1
[0,up] --> [0,up+sum]
但是一个区间内的数字为了避免重复计算
我们选择同时移动左端点
[0,up]-->[up+1,up+sum]
Q3--001:怎么实现Q2的扩展：
首先，对每个区间的排序也是不现实的，这里我们可以用一个桶记录每个数字出现的次数
因为我们每次询问的是一个区间，而我们查询的是一个区间内某个范围内的数字和（而且还有实现上述的排序），这个时候就需要用可持久化权值线段树
可以每次查询小于Mex的范围的所有数字sum
看看新扩展出来的那部分数字的和加上原来的和是否大于等于Mex，如果是继续扩展
否则输出答案
Q3-002：
查询操作变为查询区间[left+1,right+1]的和
CODE-001:
ll rt[maxn];
ll n, val[maxn], qq, indexx, TOP = 1000000001;
struct node
{
ll l, r;
ll s;
} a[maxn * 33];
void insert(ll pre, ll &now, ll l, ll r, ll num)
{
now = ++indexx;
a[now] = a[pre];
a[now].s += num;
if(l == r) return ;
ll mid = (l + r) >> 1ll;
if(num <= mid) insert(a[pre].l, a[now].l, l, mid, num);
else insert(a[pre].r, a[now].r, mid + 1, r, num);
}
ll query(ll v, ll u, ll l, ll r, ll ql, ll qr)
{
ll ans = 0;
ll sum = a[u].s - a[v].s;
if(sum == 0) return 0;
if(ql <= l && qr >= r) return sum;
ll mid = (l + r) >> 1ll;
if(ql <= mid) ans += query(a[v].l, a[u].l, l, mid, ql, qr);
if(qr > mid) ans += query(a[v].r, a[u].r, mid + 1, r, ql, qr);
return ans;
}
int main()
{
n = read();
qq = read();
rep(i, 1, n) val[i] = read(), insert(rt[i - 1], rt[i], 1ll, TOP, val[i]);
ll laast = 0ll;
while(qq--)
{
ll x, y;
x = read(), y = read();
x += laast, y += laast;
x %= n, x++, y %= n, y++;
if(x > y) swap(x, y);
ll left = 1ll, right = 1ll;
while(query(rt[x - 1], rt[y], 1ll, TOP, left, right) >= right) right = query(rt[x - 1], rt[y], 1, TOP, left, right) + 1ll ;
printf("%lld\n", right);
laast = right;
}
return 0;
}
View Code
CODE-002:
ll rt[maxn];
int n, val[maxn], qq, indexx, TOP = 1000000001;
struct node {
ll l, r;
ll s;
} a[maxn * 33];
void insert(ll pre, ll &now, int l, int r, ll num) {
now = ++indexx;
a[now] = a[pre];
a[now].s += num;
if(l==r) return ;
ll mid = (l + r) >> 1ll;
if(num <= mid) insert(a[pre].l, a[now].l, l, mid, num);
else insert(a[pre].r, a[now].r, mid + 1, r, num);
}
ll query(ll v, ll u, ll l, ll r, ll ql, ll qr) {
ll ans = 0;
ll sum = a[u].s - a[v].s;
if(sum==0) return 0;
if(ql <= l && qr >= r) return sum;
ll mid = (l + r) >> 1ll;
if(ql <= mid) ans += query(a[v].l, a[u].l, l, mid, ql, qr);
if(qr > mid) ans += query(a[v].r, a[u].r, mid + 1, r, ql, qr);
return ans;
}
int main() {
n = read();
qq = read();
rep(i, 1, n) val[i] = read(),insert(rt[i - 1], rt[i], 1ll, TOP, val[i]);
ll laast=0ll;
while(qq--) {
ll x, y;
x = read(), y = read();
x+=laast,y+=laast;
x%=n,x++,y%=n,y++;
if(x>y) swap(x,y);
ll left = 0ll, right = 0ll;
while(query(rt[x-1], rt[y], 1ll, TOP, left+1, right+1)) {
ll zhi = query(rt[x-1], rt[y], 1ll, TOP, left+1, right+1);
left = right+1ll;
right= right+ zhi;
}
printf("%lld\n",right+1ll);
laast = right+1ll;
}
return 0;
}
View Code