[DS记录]P5068 [Ynoi2015] 我回来了

**题意** ： 对于集合 $S$ ，进行以下操作 : - 每轮操作将 $S$ 中的数全部减 $d$ （常数），并删除所有 $\leq 0$ 的数。 - 若某一轮减完后，没有 $\leq 0$ 的数，则停止操作。 定义 ${\rm mogic}(S,d)$ 为上述过程持续的轮数。 维护集合 $S$ ，支持下列操作 ： - 向 $S$ 中插入数 $x$。 - 查询 $\sum\limits_{d\in[l,r]}{\rm mogic}(S,d)$ 的值。 允许离线，$m\leq 10^6,x\leq 10^5$ ，时限$\texttt{1s}$。 ------------ 对于每个 $d$ ，将值域 $[1,n]$ 分为 $O(n/d)$ 块，询问相当于查询有值的极长块前缀的长度。 总块数是 $O(\sum_{i=1}^nn/i)=O(n\log n)$ 的。 由于只有插入，有值的极长块前缀单调增长。 每次插入只需快速找出新增的有值的块，然后尝试极长块前缀，在树状数组上单点修改。树状数组的复杂度为均摊 $O(n\log^2n)$。 接下来考虑如何求新增的有值的块。 注意到允许离线，问题可以转化为求每个块第一次有值的时间。 记 $t_x$ 为 $x$ 第一次被插入的时间，使用 ST 表即可做到 $O(n\log n)$。 综上，时间复杂度为 $O(n\log^2n+m\log n)$ ，空间复杂度为 $O(n\log n)$，且常数较小。 ```cpp #include<algorithm> #include<cstdio> #define MaxM 1005000 #define MaxN 100500 using namespace std; int n; #define lbit(p) (p&-p) struct SumDS{ int o[MaxN]; void add(int p) {while(p<=n){o[p]++;p+=lbit(p);}} int qry(int p){ int ret=0; while(p){ret+=o[p];p^=lbit(p);} return ret; } }T; struct Line{int t,nxt;}l[MaxN*16]; int fir[MaxM],tl; void adl(int u,int t) {l[++tl]=(Line){t,fir[u]};fir[u]=tl;} int m,op[MaxM],sl[MaxM],sr[MaxM],lg2[MaxN],t[20][MaxN]; int qry(int l,int r){ int k=lg2[r-l+1]; return min(t[k][l],t[k][r-(1<<k)+1]); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)t[0][i]=m+1; for (int i=1,p;i<=m;i++){ scanf("%d",&op[i]); if (op[i]==1){scanf("%d",&p);t[0][p]=min(t[0][p],i);} else scanf("%d%d",&sl[i],&sr[i]); } for (int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1; for (int j=1;(1<<j)<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++) t[j][i]=min(t[j-1][i],t[j-1][i+(1<<j-1)]); for (int d=1;d<=n;d++){ int tim=0; for (int i=1,c=1;i<=n;i+=d,c++){ int l=i,r=min(i+d-1,n); tim=max(tim,qry(l,r)); if (tim<=m)adl(tim,d); } } for (int i=1;i<=m;i++){ for (int j=fir[i];j;j=l[j].nxt)T.add(l[j].t); if (op[i]==2)printf("%d\n",T.qry(sr[i])-T.qry(sl[i]-1)+sr[i]-sl[i]+1); }return 0; } ```