## 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); } }