RT,RE 抱灵，代码求调 qwq

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int B=300;
const int Q=200005;
const int N=200005;
const int cntChange=60000005;
inline int get(int x){return (x+B-1)/B;}
int n,q;
inline int getl(int x){return (x-1)*B+1;}
inline int getr(int x){return min(x*B,n);}
int a[N];

int changes[200005];
bool flag[200005];
int head[200005];
int nxt[cntChange];
int val[cntChange];
int cntch;
void ins(int x,int y)
{
    assert(cntch<cntChange);
    val[++cntch]=y;
    nxt[cntch]=head[x];
    head[x]=cntch;
}
void upd(int x)
{
    for(int i=head[x];i&&flag[val[i]];i=nxt[i])head[x]=nxt[i];
}
struct Stack
{
    int stk[200005];
    int Top;
    void push(int x)
    {
        stk[++Top]=x;
    }
    void pop()
    {
        assert(Top);
        Top--;
    }
    int top()
    {
        return stk[Top];
    }
    bool empty()
    {
        return Top==0;
    }
};
struct Block
{
    Stack stk;
    ll ans;
    int posl,posr;
    int len;
    void change(int id,int x)
    {
        ans=1ll*(posr-posl+1)*x;
        stk.push(id);
    }
    bool empty()
    {
        return stk.empty();
    }
    int res[505],p,lst;
}b[505];
int id[505];
bool cmp(int x,int y)
{
    return val[head[x]]<val[head[y]];
}
void rebuild(int x)
{
    // printf("rebuild(%d)\n",x);
    b[x].lst=b[x].stk.top();
    for(int i=1;i<=b[x].len;i++)id[i]=i+b[x].posl-1;
    assert(b[x].len<=B);
    sort(id+1,id+b[x].len+1,cmp);
    for(int i=b[x].len;i>=0;i--)b[x].res[i]=b[x].res[i+1]+(val[head[id[i+1]]]?changes[val[head[id[i+1]]]]:a[id[i+1]]);
    // for(int i=0;i<=b[x].len;i++)printf("b[x].res[%d]=%d\n",i,b[x].res[i]);
    for(b[x].p=1;b[x].p<=b[x].len&&val[head[id[b[x].p]]]<b[x].stk.top();b[x].p++);
    if(val[head[id[b[x].p]]]>=b[x].stk.top())b[x].p--;
    b[x].ans=1ll*b[x].p*changes[b[x].stk.top()]+b[x].res[b[x].p];
}
void init()
{
    for(int i=1;i<=get(n);i++)
    {
        b[i].posl=getl(i);
        b[i].posr=getr(i);
        b[i].len=b[i].posr-b[i].posl+1;
        rebuild(i);
    }
}
void cover(int l,int r,int x,int id)
{
    // printf("cover(%d,%d,%d,%d)\n",l,r,x,id);
    changes[id]=x;
    int bl=get(l);
    int br=get(r);
    if(bl==br)
    {
        for(int i=l;i<=r;i++)ins(i,id);
        rebuild(bl);
        return;
    }
    for(int i=bl+1;i<=br-1;i++)
    {
        b[i].change(id,x);
    }
    for(int i=l;i<=getr(bl);i++)ins(i,id);
    for(int i=getl(br);i<=r;i++)ins(i,id);
    rebuild(bl);
    rebuild(br);
}
void blkundo(int x)
{
    while(flag[b[x].stk.top()])b[x].stk.pop();
    // printf("blkundo(%d)\n",x);
    if(b[x].stk.top()>b[x].lst)
    {
        b[x].ans=1ll*changes[b[x].stk.top()]*b[x].len;
        return;
    }
    // printf("blkundo(%d)\n",x);

    // printf("b[x].p=%d\n",b[x].p);
    for(;b[x].p&&val[head[id[b[x].p]]]>=b[x].stk.top();b[x].p--);
    // printf("blkundo(%d)\n",x);
    // printf("changes[b[x].stk.top()]=%d\n",changes[b[x].stk.top()]);
    b[x].ans=1ll*b[x].p*changes[b[x].stk.top()]+b[x].res[b[x].p];
}
void undo(int l,int r,int id)
{
    // printf("undo(%d,%d,%d)\n",l,r,id);
    flag[id]=true;
    int bl=get(l);
    int br=get(r);
    if(bl==br)
    {
        for(int i=l;i<=r;i++)upd(i);
        rebuild(bl);
        return;
    }
    for(int i=bl+1;i<=br-1;i++)blkundo(i);
    for(int i=l;i<=getr(bl);i++)upd(i);
    rebuild(bl);
    for(int i=getl(br);i<=r;i++)upd(i);
    rebuild(br);
}
ll blockqu(int l,int r,int bl)
{
    assert(get(l)==bl);
    assert(get(r)==bl);
    assert(l<=r);
    ll ret=0;
    for(int i=l;i<=r;i++)
        if(b[bl].empty())
        {
            if(!head[i])ret+=a[i];
            else ret+=changes[val[head[i]]];
        }
        else
        {
            if(!head[i])ret+=changes[b[bl].stk.top()];
            else ret+=changes[max(b[bl].stk.top(),val[head[i]])];
        }
    // printf("blockqu(%d,%d)=%lld\n",l,r,ret);
    return ret;
}
ll query(int l,int r)
{
    // printf("query(%d,%d)\n",l,r);
    int bl=get(l),br=get(r);
    ll ret=0;
    if(bl==br)
    {
        ret=blockqu(l,r,bl);
        return ret;
    }
    for(int i=bl+1;i<=br-1;i++)ret+=b[i].ans;
    ret+=blockqu(l,getr(bl),bl);
    ret+=blockqu(getl(br),r,br);
    return ret;
}
void print()
{
    for(int i=1;i<=get(n);i++)printf("%d~%d:%d\n",b[i].posl,b[i].posr,b[i].ans);
}
ll lastans;
int idcnt;
int chl[200005],chr[200005];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();
    for(int opt,x,y,z,i=1;i<=q;i++)
    {
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            scanf("%d%d",&y,&z);
            x=x^lastans;
            y=y^lastans;
            idcnt++;
            chl[idcnt]=x;
            chr[idcnt]=y;
            while(x>y);
            cover(x,y,z,idcnt);
        }
        else if(opt==2)
        {
            scanf("%d",&y);
            x=x^lastans;
            y=y^lastans;
            while(x>y);
            lastans=query(x,y);
            printf("%lld\n",lastans);
        }
        else
        {
            x=x^lastans;
            undo(chl[x],chr[x],x);
        }
        // akari.print();
    }
    return 0;
}