题意：有一个数列，支持两种操作。

1. 在数列一个数后插入一个新数；
2. 选一个区间，每次将区间所有数的值都减 $ 1 $ ，有一个值变为 $ 0 $ 后重复操作，询问会操作几次。询问对接下来的操作不干涉。

题解：

算法一：

询问可转化为一段区间没出现的数最小是多少。每次 $ O(n) $ 暴力即可。

算法二：

没有强制在线就是舒服。

将所有操作离线，预处理出操作在数列中的位置，所有插入操作变为修改操作。这个过程可以用 $ Splay $ 维护。注意数列中元素初始为无穷大。

我们发现信息很难有树形结构维护，于是考虑莫队。莫队维护一段区间每个值出现次数和是否出现，然后我们可以用各种方法维护（树状数组+前缀和，线段树），时间复杂度 $ O(n^{\frac{5}{3}} \log {n}) $。

当然我们可能发现 $ TLE $ 。

优化1：读入优化，输出优化，不必多说。

优化2：我们维护的数据结构不够优秀，莫队的每次修改（一共 $ n^{\frac{5}{3}} $ 次）都需要 $ O(\log n) $ 的时间。我们发现询问操作很少（只有 $ n $ 次），于是我们可以用 $ O(1) $ 修改、 $ O(\sqrt {n}) $ 查询的分块维护，时间复杂度 $ O(n^{\frac{5}{3}} + n \sqrt{n}) $。

优化3：O2优化。

#include
    
     #pragma GCC optimize(3)using namespace std;const int N=100050,INF=100002;int n,blo,a[N],ans[N],l=1,r=0,now=0;int bl[N],L[N],R[N],b[400],cnt[N],blosize;char pr[N*10],lpr=0;namespace Splay {    #define lc ch[u][0]    #define rc ch[u][1]    int fa[N],ch[N][2],sz[N],rt=0,tot=0;    void pushup(int u) { sz[u]=1+sz[lc]+sz[rc]; }    void rotate(int u) {        int y=fa[u],z=fa[y],k=ch[y][1]==u,w=ch[u][k^1];        if(z) ch[z][ch[z][1]==y]=u; ch[y][k]=w,ch[u][k^1]=y;        if(w) fa[w]=y; fa[y]=u,fa[u]=z;        pushup(y),pushup(u);    }    void splay(int u,int goal) {        for(int y,z;fa[u]!=goal;rotate(u)) {            y=fa[u],z=fa[y];            if(z!=goal) rotate((ch[y][0]==u)^(ch[z][0]==y)? u:y);        }        if(!goal) rt=u;    }    int getid(int u,int s) {        if(!u) return 0; if(sz[lc]+1==s) return u;        return sz[lc]>=s? getid(lc,s):getid(rc,s-sz[lc]-1);    }    int getrnk(int u) { splay(u,0);return sz[lc]+1; }    void insert(int &u,int ff,int w) {        if(!u) { u=++tot,sz[u]=1,fa[u]=ff,splay(u,0);return ; }        if(w<=sz[lc]) insert(lc,u,w); else insert(rc,u,w-sz[lc]-1);    }    #undef lc    #undef rc}struct ASK { int opt,x,y; };ASK k[N];struct M { int t,x,val; };M mod[N]; int lm=0;struct P {    int l,r,id,type;    friend bool operator<(P xx,P yy) {        if(xx.l/blo!=yy.l/blo) return xx.l
     
      '9') c=getchar();    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();    return x;}void add(int w) { ++cnt[w]; if(cnt[w]==1) ++b[bl[w]]; }void del(int w) { --cnt[w]; if(!cnt[w]) --b[bl[w]]; }void update(int nw) {    if(mod[nw].x<=r&&mod[nw].x>=l)  del(a[mod[nw].x]),add(mod[nw].val);    swap(a[mod[nw].x],mod[nw].val);}int ask() {    int tans=100001;    for(int i=1;i<=bl[N-50];i++)        if(b[i]
      
       q[i].l;) add(a[--l]);        for(;r>q[i].r;) del(a[r--]); for(;l
       
        q[i].type) update(now--);        ans[q[i].id]=ask();    }    for(int i=1;i<=lq;i++) printf("%d\n",ans[i]);    return 0;}