Stone Games（思维+可持久化线段树）

题目

原题链接

问题描述

主要意思就是给定一个正整数砝码集合，问这堆砝码无法凑出的最小正整数。

分析

先分析出一个特例：当砝码集合中不存在$1$时，那么答案就是$1$。

以$[0,pre]$表示当前集合可以凑出该区间内的所有数，当我们再加入一个数$x$时，相当于将这个区间整体右移，可以得到$[x,pre+x]$，若两个区间存在重叠或相邻部分，则可以说明加入$x$到集合中后可以凑出$[0,pre+x]$内的所有数。

我最开始的思路是先对$[l,r]$内的数依照升序排列，然后依次处理，但简单计算一下时间复杂度，题目总共有$Q$轮游戏，若每轮都进行一次排序，而且还要依次判断，最终的时间复杂度为$O(Qnlogn)$，将会导致超时

for(ll i=l;i<=r;i++)b[i]=a[i];
sort(b+l,b+r+1);
if(b[l]!=1){
    printf("1\n");ans=1;return;
}
ll ma=1,pre=1;
for(ll i=l+1;i<=r;i++){
    ma+=b[i];if(b[i]>pre+1){
    ans=pre+1;printf("%lld\n",ans);return;}pre=ma;
}
ans=ma+1;
printf("%lld\n",ans);

深入分析，对于$[0,pre]$这个区间来说，只要我们向集合内添加的数$x$处于$[1,pre+1]$中，就可以保证右移后可以得到一个满足要求的区间$0,pre+x$，我之前是通过排序来保证遍历过程的合法性，但如果我有一种方法，可以直接得知在区间$[l,r]$内未使用过且大小处于$[1,pre+1]$的数，因为这些数都是可以直接用于合法更新区间$[0,pre]$，假设这些数的和为$sum$，更新之后的区间就是$[0,pre+sum]$，重复寻找步骤；当发现$sum$为$0$时，则说明不存在合法数据可以用于更新区间，就可以结束循环，答案就是$pre+1$。

之前采用排序的时间复杂度为$O(nlogn)$，将导致超时，假设$f()$表示用于求出在区间$[l,r]$内未使用过且大小处于$[1,pre+1]$的数的$sum$的方法，由于我们每次都只要求剩余的里面未使用过的数，所以差不多经过$logn$次就可以完成，所以此时的时间复杂度为$O(Qlogn?O(f()))$。
只要$f()$的时间复杂度小于$O(n)$就差不多了。

再进一步分析，其实我们求出的$pre+sum$也就是区间$[l,r]$内值小于$pre+1$的所有值的和

接下来就是模板的套用——可持久化线段树。

有一个容易忽视的点，题目中的$Q$很大，如果每回合都创建一些临时变量，将会导致内存超限。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e6+5;
const  ll inf=1e9+10;
ll a[N],n,t,root[N*40],cnt;
struct Tree{
    int l,r;ll sum;
}tr[N*40];
void insert(ll l,ll r,int pre,int &now,ll p){
    tr[++cnt]=tr[pre];now=cnt;tr[now].sum+=p;if(l==r)return ;ll mid=(l+r)>>1;if(p<=mid) insert(l,mid,tr[pre].l,tr[now].l,p);else insert(mid+1,r,tr[pre].r,tr[now].r,p);
}ll query(ll st,ll ed,ll l,ll r,int x,int y){
    if(st<=l&&r<=ed){
    return tr[y].sum-tr[x].sum;}ll mid=(l+r)>>1,ans=0;if(st<=mid)ans+=query(st,ed,l,mid,tr[x].l,tr[y].l);if(ed>mid)ans+=query(st,ed,mid+1,r,tr[x].r,tr[y].r);return ans;
}int main(){
    scanf("%lld%lld",&n,&t);for(ll i=1;i<=n;i++){
    scanf("%lld",&(a[i]));}for(int i=1;i<=n;i++){
    insert(1,inf,root[i-1],root[i],a[i]);}ll l,r,tmpa,tmpb,ans=0,tmp,pre;while(t--){
    scanf("%lld%lld",&l,&r);tmpa=1+(ans+l)%n,tmpb=1+(ans+r)%n;l=min(tmpa,tmpb);r=max(tmpa,tmpb);pre=0;while(1){
    tmp=query(1,min(inf,pre+1),1,inf,root[l-1],root[r]);if(tmp==pre)break;pre=tmp;}ans=pre+1;printf("%lld\n",ans);}	return 0;
}