2021 ICPC Kunming m stone games (persistent weight segment tree)

At that time, I just looked at it and felt it was a line segment tree, but I couldn't write it. Now let's make up for it

Main idea of the title:

Give you a sequence of 1e6 in length, a (a [i] < = 1e9), and q (q < = 1E5) times. Each time, ask the interval l,r, and ask the minimum positive integer that cannot be represented by the subsequence from a[l] to a[r] (which means that it can be expressed as the sum of one or more numbers in the sequence), and force it online.

practice

Let's simplify the problem first: how to find the minimum value that a sequence of length n cannot represent?
First you can see:
Interval: 1 1 3 20
1. If there is no 1 in the interval, the minimum positive integer that must not be represented is 1
2. If 1 appears and there is another 1, I can use the existing 1 and 1 to form 2 (of course, a 2 is also OK)
3. If it can form 1 ~ 2, there is still a 3. We can use this 3 and the previous (0 ~ 2) to express 3, 4 and 5
4. Now 5 is OK. I have the last 20. Then we can get 0 ~ 5 + 20, that is, 20 ~ 25. At this time, we find that 6 does not appear, and the answer is 6

Of course, I can't lift it all the way 1e9, so let's summarize the rules:
1. If I can express from 1 to K, then if I have another number m, I must be able to combine this m and these 1~k into all numbers of m ~m+k.
2. I can now express 1~k, so if the sum of all my numbers from 1~k + 1 is sum, I consider whether I can express 1 ~sum:
/-------If sum < = k, what does it mean?
First, the number k+1 does not appear
Secondly, the previous numbers add up to only k or less
The answer is k+1
/-------If sum > k
According to the above logic, we can express all the values of 1~sum
Why:
In the last step, I created a K (k is the last sum). Suppose I now have a number m added in
I can express x + 0 ~ x + K (this x is less than or equal to k+1, so it must be represented by itself or before),
We can express 1~k, but also from an X representation less than or equal to k+1 to x+k
So we can express k+x
Take k+x as the new k
If I add another y, we can also express y+0~y+k
So I can express k+x+y
So, since I add in less than k
I can express how much k + I add
Because sum-k is added
So, we can express sum-k+k=sum

Then turn k into sum and continue to repeat this series of steps

Therefore, we need to extract the sum of 1-k in all intervals for each operation
Then we can use the persistent weight segment tree to solve the problem

Let's talk about the specific operation. Let's make a line segment tree summary later

Complexity

It should be q (number of queries) * log (line segment tree query) * strange sum increase process
This growth should be started by Fibonacci, and it should be log level (I'm not very good at it anyway)

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct tree{
	ll val;
	int lc,rc;
};tree t[66000005];
int rt[1000005],a[1000005];
int n,q,cnt=0;
ll maxv=1e9+7;
void build(int l,int r,int pos,int val,int &x,int y){
	x=++cnt;
	t[x].lc=t[y].lc;
	t[x].rc=t[y].rc;
	t[x].val=t[y].val+val;
	if(l==r) return;
	int mid=(l+r)/2;
	if(pos<=mid) build(l,mid,pos,val,t[x].lc,t[y].lc);
	else build(mid+1,r,pos,val,t[x].rc,t[y].rc);
}
ll query(int l,int r,int ql,int qr,int x,int y){
	if(l>=ql&&r<=qr){
		return t[y].val-t[x].val;
	}
	int mid=(l+r)/2;
	ll ret=0;
	if(ql<=mid) ret+=query(l,mid,ql,qr,t[x].lc,t[y].lc);
	if(qr>mid) ret+=query(mid+1,r,ql,qr,t[x].rc,t[y].rc);
	return ret;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		build(1,maxv,a[i],a[i],rt[i],rt[i-1]);
	} 
	ll ans=0;
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		l=(l+ans)%n+1;
		r=(r+ans)%n+1;
		if(l>r) swap(l,r);
		ll x=0;
		while(1){
			ll now=query(1,maxv,1,min(x+1,maxv),rt[l-1],rt[r]);
			if(now==x) break;
			x=now;
		}
		ans=x+1;
		printf("%lld\n",ans);
	}
}