[nowcoder 2020] 牛牛的凑数游戏

一、题目

点此看题

二、解法

本题咋看上去难有思路，但是结合数据范围的提示：保证输入的a_i单调非降，不妨朝这个方向想一想。

设现在能表示的区间是$[1,r]$，如果新加入了一个数$b$，那么新产生的区间是$[b,r+b]$，如果$r+1<b$就可以直接不算了，因为后面的数不会下降，而空出来的$r+1$是永远无法填补的，否则我们把$r$扩大$b$。现在想必你知道为什么区间只会有一段。

我们模拟上的的过程，最多拿到$40$分，我们考虑用数据结构加速我们的遍历，我们称上一次遍历的$r$是$lst$，那么$[lst+1,r+1]$中间的数算出来加上去，如果没有数的话就跳出。这样的复杂度怎么保证？我们以$lst$为参考系，那么花了$2$步就翻倍啦！这样遍历的次数一定是$O(\log n)$

数据结构一定选主席树，时间复杂度$O(n{\log }^{2}n)$，还有一些细节看代码

#include <cstdio> const int M = 100005; const int up = 1e9; #define int long long int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,m,cnt,rt[M],ls[40*M],rs[40*M],sum[40*M]; void insert(int &x,int y,int l,int r,int id) { x=++cnt; sum[x]=sum[y]+id; ls[x]=ls[y];rs[x]=rs[y]; if(l==r) return ; int mid=(l+r)>>1; if(mid>=id) insert(ls[x],ls[y],l,mid,id); else insert(rs[x],rs[y],mid+1,r,id); } int ask(int x,int l,int r,int L,int R) { if(!x || L>r || l>R) return 0; if(L<=l && r<=R) return sum[x]; int mid=(l+r)>>1; return ask(ls[x],l,mid,L,R)+ask(rs[x],mid+1,r,L,R); } signed main() { n=read();m=read(); for(int i=1;i<=n;i++) { int x=read(); insert(rt[i],rt[i-1],1,up,x); } for(int i=1;i<=m;i++) { int l=read(),r=read(),mx=0,lt=0,f=0; while(mx<=up) { int t=ask(rt[r],1,up,lt+1,mx+1)-ask(rt[l-1],1,up,lt+1,mx+1); if(!t) { printf("%lld\n",mx+1); f=1;break; } lt=mx+1;mx+=t; } if(f==0) printf("%lld\n",mx+1+ask(rt[r],1,up,lt+1,up)-ask(rt[l-1],1,up,lt+1,up)); //说明mx超过了上界，但还是要统计遗留的部分 } }