啥憋笑题，洗澡前看了一眼结果头还没洗完就胡出来了。

唉最近只会做这种没啥思维含量的题了，月赛啥的都打的依托，如何进步啊。

这个删除看起来很恶心，会整段平移。

考虑进行相对运动，把询问点后移即可。

于是开个线段树维护每个点被删除的人的个数，这个就是偏移量。

于是变成区间增加后缀，查询某个点上某一位的颜色。

不带修，所以啥时候这一位出现了那么这一位的颜色就定下来了。

考虑直接维护每个点的长度，长度有单调性可以二分，我们二分找出第一个让该位置长度符合要求的增加操作，这个操作的颜色显然就是答案。

每个操作后的版本都有可能被查询，上主席树即可，二分版本编号。

注意是区间修改，标记永久化。

于是 $O(n\log^2 n)$ 做完了。

代码还没写，应该是对的，题解区没看到这种弱智做法。

写的时候发现有个细节锅，这里补一嘴。

你发现询问点移位溢出后不能虚空移位，也就是有个上限，这样原做法就挂掉了。

那咋办？不会还要上个 Segment Tree Beats 吧？问题是我不会这个啊。

考虑到查询是单点，所以直接线段树也是可以的。

具体的，考虑原问题是要干什么：

• 区间上限加；
• 区间加，对上限取 $\min$；
• 单点求值。

考虑维护上限与真实值的差 $c_i$，此时变成区间加减，对 $0$ 取 $\max$。

插入一句话，我不知道为啥让 deepseek 检测题解是否随机说话会在这里被毙，感觉很难绷。

这里的真实值指的是原问题的真实值，而原问题解决的是偏移量问题，所以真实值指的是偏移量。

而不是实际队列剩余长度！！！！！

你真要论意义这里指的是真实删除数量，而 $c_i$ 才是剩余队列长度啊。

考虑每个节点同时维护一个移除懒标记和一个增加懒标记。

打移除标记的时候先和这个节点的增加标记爆了，有剩下的再打到移除懒标记上；打增加懒标记的时候不管已经有的移除懒标记，直接加入增加标记。

单点查询到的时候再下放标记，标记落到叶子上的时候如果移除标记和原本的值爆完还有剩的直接无视丢掉，然后把增加标记当成值返回即可。

因为是单点查询，所以查询时该下放的地方标记都有充分的下放处理过了，正确性得到保证。

:::info[为啥选择先下放增加的标记？] 因为减的时候直接对撞消耗掉了，于是残存的减法标记一定是比加法标记早出现的，而早出现的减法标记不能作用于后来的加法标记上。

下放标记时，因为访问过的点都会下放，所以下面的标记打上的时间一定比往下传的这个标记时间早，所以减法可以优先进行对撞，然后再下放加法。

于是原理上没啥矛盾的地方。

多余打的删除标记，容易发现因为先下传所以会在叶子节点无效积累，不影响结果。 :::

得到 $c_i$ 以后，我们同步维护一个上限，那么就能够得到真实值了。

而这个上限就是一个平凡的线段树可以解决的。问题不大。

最后求得的真实值就是目标偏移量。

然后就是同学指出题解区里面已经有在线主席树这样的诡谲做法了，找的不仔细谢罪。

算了一下前前后后调了 6h，线段树简单变式写的不熟挂一万年，菜完了。如何提高代码能力？

然后就是我人傻常数大，被卡常了，那咋办。
下面的这份卡了好久才过，大家应该随便草飞吧 /kel

#include<bits/stdc++.h>
#define ll unsigned long long
#define int unsigned int
using namespace std;
#define N 250005
int col[N];
int rt[N];
int tp;
struct his_tr{
    ll lz[(N<<5)+10];
    ll tr[(N<<5)+10];
    int ls[(N<<5)+10];
    int rs[(N<<5)+10];
    int top=0;
    int cop(int x){
        int ret=++top;
        tr[ret]=tr[x];
        ls[ret]=ls[x];
        rs[ret]=rs[x];
        lz[ret]=lz[x];
        return ret;
    }
    void pushup(int x,int l,int r){
        tr[x]=tr[ls[x]]+tr[rs[x]]+lz[x]*(r-l+1);
    }
    int upd(int x,int l,int r,int L,int R,int v){
        x=cop(x);
        if(L<=l&&r<=R){
            tr[x]+=v*(r-l+1);
            lz[x]+=v;
            return x;
        }
        int mid=(l+r)>>1;
        if(L<=mid)ls[x]=upd(ls[x],l,mid,L,R,v);
        if(R>mid)rs[x]=upd(rs[x],mid+1,r,L,R,v);
        pushup(x,l,r);
        return x;
    }
    ll qry(int x,int l,int r,int t,ll tag=0){
        if(t==l&&r==t)return tr[x]+tag;
        int mid=(l+r)>>1;
        if(t<=mid)return qry(ls[x],l,mid,t,tag+lz[x]);
        else return qry(rs[x],mid+1,r,t,tag+lz[x]);
    }
}tr;
struct seg_tr{
    ll lz_add[(N<<2)+5],lz_del[(N<<2)+5];
    ll a[(N<<2)+5];
    void down_del(int u,ll x){
        if(x<=lz_add[u]){
            lz_add[u]-=x;
            return;
        }
        x-=lz_add[u];
        lz_add[u]=0;
        lz_del[u]+=x;
    }
    void down_add(int u,ll x){
        lz_add[u]+=x;
    }
    void down(int u,ll x){
        a[u]+=x;
    }
    void pushdown(int u){
        down_del(u<<1,lz_del[u]);
        down_del(u<<1|1,lz_del[u]);
        lz_del[u]=0;
        down_add(u<<1,lz_add[u]);
        down_add(u<<1|1,lz_add[u]);
        lz_add[u]=0;
        down(u<<1,a[u]);
        down(u<<1|1,a[u]);
        a[u]=0;
    }
    void upd_add(int u,int l,int r,int L,int R,ll x){
        if(L<=l&&r<=R){
            lz_add[u]+=x;
            a[u]+=x;
            return;
        }
        pushdown(u);
        int mid=(l+r)>>1;
        if(L<=mid)upd_add(u<<1,l,mid,L,R,x);
        if(R>mid)upd_add(u<<1|1,mid+1,r,L,R,x);
    }
    void upd_del(int u,int l,int r,int L,int R,ll x){
        if(L<=l&&r<=R){
            down_del(u,x);
            return;
        }
        pushdown(u);
        int mid=(l+r)>>1;
        if(L<=mid)upd_del(u<<1,l,mid,L,R,x);
        if(R>mid)upd_del(u<<1|1,mid+1,r,L,R,x);
    }
    ll qry(int u,int l,int r,int t){
        if(l==r)return a[u]-lz_add[u];
        pushdown(u);
        int mid=(l+r)>>1;
        if(t<=mid)return qry(u<<1,l,mid,t);
        else return qry(u<<1|1,mid+1,r,t);
    }
}tr1;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,c,k;
            cin>>l>>r>>c>>k;
            tp++;
            col[tp]=c;
            rt[tp]=tr.upd(rt[tp-1],1,n,l,r,k);
            tr1.upd_add(1,1,n,l,r,k);
        }else if(op==2){
            int l,r,x;
            cin>>l>>r>>x;
            tr1.upd_del(1,1,n,l,r,x);
        }else{
            int id; ll x;
            cin>>id>>x;
            x+=tr1.qry(1,1,n,id);
            if(tr.qry(rt[tp],1,n,id)<x)cout<<"0\n";
            else{
                int l=1,r=tp;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(tr.qry(rt[mid],1,n,id)<x)l=mid+1;
                    else r=mid;
                }
                cout<<col[r]<<'\n';
            }
        }
    }
    return 0;
}
//「我刚才不是说……要把他们尽数杀光吗？」
//「嗯，是啊。我也觉得那样比较快。」

//「那你又为何——！」
//「可是，总觉得你好像很讨厌这么做。」

// 可蓉露齿一笑。
//「你讨厌的东西就是我讨厌的东西。反正我就像个不肖军人，为了家人违抗命令算不上什么。」