牛客挑战赛59 D

放一个常数巨大不能通过的做法。

首先子序列信息显然可以动态 dp。

然后有插入操作，于是显然得用平衡树来维护区间信息。

打的 WBLT，然后结果实测不加平衡措施还更快？？？（除掉 S=0 外，均有数据随机）

struct Info{ullt O,R,Z,OR,RZ,ORZ;__always_inline friend Info operator+(Info a,Info b){return Info{a.O+b.O,a.R+b.R,a.Z+b.Z,a.OR+b.OR+a.O*b.R,a.RZ+b.RZ+a.R*b.Z,a.ORZ+b.ORZ+a.O*b.RZ+a.OR*b.Z};}};
struct Seg
{
    Seg*L,*R;uint len;Info v;
    Seg():L(NULL),R(NULL),len(1),v({1,0,0,0,0,0}){}
    Seg(Info v):L(NULL),R(NULL),len(1),v(v){}
    Seg(chr*bgn,chr*end):L(NULL),R(NULL),len(end-bgn){
        if(len>1)L=new Seg(bgn,bgn+(len>>1)),R=new Seg(bgn+(len>>1),end),v=L->v+R->v;
        else v={*bgn=='o',*bgn=='r',*bgn=='z',0,0,0};
    }
}*S;
voi insert(Seg*S,uint p)
{
    if(S->len==1){S->L=new Seg(S->v),S->v=S->v+(S->R=new Seg())->v,S->len=2;return;}
    uint LEN=S->L->len;
    p<LEN?insert(S->L,p):insert(S->R,p-LEN);S->len++,S->v=S->L->v+S->R->v;
}
Info find(Seg*S,uint l,uint r)
{
    while(l||r<S->len){
        uint LEN=S->L->len;
        if(l<LEN)
            if(r<=LEN)S=S->L;
            else return find(S->L,l,LEN)+find(S->R,0,r-LEN);
        else l-=LEN,r-=LEN,S=S->R;
    }
    return S->v;
}
uint SA,SB,SC;
__always_inline uint rnd(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;uint t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;}
chr _s[1000005];
int main()
{ 
    uint n,q; 
    scanf("%u%u%u%u%u",&n,&q,&SA,&SB,&SC);
    if(!SA&&!SB&&!SC)
    {
        uint v=0;
        while(q)v^=q--;
        printf("%u\n",v);
        return 0;
    }
    for(uint i=0;i<n;i++)
    {
        uint si=rnd()%3;
        if(si==0)_s[i]='o';
        if(si==1)_s[i]='r';
        if(si==2)_s[i]='z';
    }
    S=new Seg(_s,_s+n);
    ullt ans=0;
    for(uint i=1;i<=q;++i)
    {
        if(!(rnd()&1))insert(S,rnd()%n),ans^=i;
        else
        {
            uint l=rnd()%n+1,r=rnd()%n+1;
            if(l>r)std::swap(l,r);
            ans^=find(S,l-1,r).ORZ+i;
        }
    }
    printf("%llu\n",ans);
    return 0;
}

/*
6 5
3488991686 1344677723 3466680979
*/