xjoi 省选模拟赛_13

#include <bits/stdc++.h>
#define N 1100010
using namespace std;
typedef unsigned long long ull;
const ull xx=23333;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘&&ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
int n,m,Q,lsd1,lsd2,pla[N],plb[N],k;
int A[N],B[N],faa[N],fab[N],rt1,rt2;
int ca[N][2],cb[N][2],sza[N],szb[N];
bool rev[N];
ull hasha[N],hashb[N],hashr[N];
ull pows[N];
inline void pushdown(int rt)
{
    if(rev[rt])
    {
        swap(hashr[rt],hasha[rt]);
        rev[ca[rt][0]]^=1;
        rev[ca[rt][1]]^=1;
        swap(ca[rt][0],ca[rt][1]);
        rev[rt]=0;
    }
}
inline void updata1(int mid)
{
    sza[mid]=sza[ca[mid][0]]+sza[ca[mid][1]]+1;
    pushdown(ca[mid][0]);pushdown(ca[mid][1]);
    hasha[mid]=pows[sza[ca[mid][0]]]*A[mid]+hasha[ca[mid][0]]+pows[sza[ca[mid][0]]+1]*hasha[ca[mid][1]];
    hashr[mid]=pows[sza[ca[mid][1]]]*A[mid]+hashr[ca[mid][1]]+pows[sza[ca[mid][1]]+1]*hashr[ca[mid][0]];
}
inline void updata2(int mid)
{
    szb[mid]=szb[cb[mid][0]]+szb[cb[mid][1]]+1;
    hashb[mid]=pows[szb[cb[mid][0]]]*B[mid]+hashb[cb[mid][0]]+pows[szb[cb[mid][0]]+1]*hashb[cb[mid][1]];   
}
int built1(int fa,int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1,g=mid;sza[mid]=1;
    hasha[mid]=hashr[mid]=A[mid];
    ca[g][0]=built1(mid,l,mid-1);ca[g][1]=built1(mid,mid+1,r);
    updata1(mid);
    faa[mid]=fa; return g;
}
int built2(int fa,int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1,g=mid;szb[mid]=1;
    hashb[mid]=B[mid];
    cb[g][0]=built2(mid,l,mid-1);cb[g][1]=built2(mid,mid+1,r);
    updata2(mid);
    fab[mid]=fa; return g; 
}
// splay B
void rotateb(int x,int &k)
{
    int y=fab[x],z=fab[y],l,r;
    l=(cb[y][1]==x);r=l^1;
    if(y==k)k=x;
    else cb[z][cb[z][1]==y]=x;
    fab[cb[x][r]]=y;fab[y]=x;fab[x]=z;
    cb[y][l]=cb[x][r];cb[x][r]=y;
    updata2(y);updata2(x);
}
void splayb(int x,int &k)
{
    while(x!=k)
    {
        int y=fab[x],z=fab[y];
        if(y!=k)
        {
            if((cb[y][0]==x)^(cb[z][0]==y))rotateb(x,k);
            else rotateb(y,k);
        }
        rotateb(x,k);
    }
}
int findb(int now,int rk)
{
    if(szb[cb[now][0]]+1==rk) return now;
    if(szb[cb[now][0]]>=rk) findb(cb[now][0],rk);
    else findb(cb[now][1],rk-szb[cb[now][0]]-1);
}
void splitb(int l,int r)
{
    int x=findb(rt2,l-1),y=findb(rt2,r+1);
    splayb(x,rt2);
    splayb(y,cb[rt2][1]);
    updata2(rt2);
}
// splay A
void rotatea(int x,int &k)
{
    int y=faa[x],z=faa[y],l,r;
    pushdown(z); pushdown(y);
    l=(ca[y][1]==x);r=l^1;
    if(y==k)k=x;
    else ca[z][ca[z][1]==y]=x;
    faa[ca[x][r]]=y;faa[y]=x;faa[x]=z;
    ca[y][l]=ca[x][r];ca[x][r]=y;
    updata1(y);updata1(x);
}
void splaya(int x,int &k)
{
    while(x!=k)
    {
        int y=faa[x],z=faa[y];
        if(y!=k)
        {
            if((ca[y][0]==x)^(ca[z][0]==y))rotatea(x,k);
            else rotatea(y,k);
        }
        rotatea(x,k);
    }
}
int finda(int now,int rk)
{
    pushdown(now);
    if(sza[ca[now][0]]+1==rk) return now;
    if(sza[ca[now][0]]>=rk) finda(ca[now][0],rk);
    else finda(ca[now][1],rk-sza[ca[now][0]]-1);
}
void splita(int l,int r)
{
    int x=finda(rt1,l-1),y=finda(rt1,r+1);
    splaya(x,rt1);
    splaya(y,ca[rt1][1]);
    updata1(rt1);
}
void erase()
{
    int xs; scanf("%d",&xs);
    int x=finda(rt1,xs); splaya(x,rt1);
    int rk=sza[ca[rt1][0]]+1;
    int y=finda(rt1,rk+2); splaya(y,ca[rt1][1]);
    ca[ca[rt1][1]][0]=0;updata1(ca[rt1][1]);
    updata1(rt1);n--;
}
void insert()
{
    int xs,ys; scanf("%d%d",&xs,&ys);
    int x=finda(rt1,xs); splaya(x,rt1);
    A[++lsd1]=ys; int rk=sza[ca[rt1][0]]+1;
    int y=finda(rt1,rk+1); splaya(y,ca[rt1][1]);
    faa[lsd1]=y; ca[y][0]=lsd1; updata1(lsd1);
    updata1(y); updata1(rt1); n++;
}
bool check(int l,int r,int len)
{
    splita(l,l+len-1);
    splitb(r,r+len-1);
    if(hasha[ca[ca[rt1][1]][0]]==hashb[cb[cb[rt2][1]][0]])
        return 1;
    return 0;
}
int query()
{
    int l,r; scanf("%d %d",&l,&r); l++;r++;
    int L=1,R=min(n-l+2,m-r+2),ans=0;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(check(l,r,mid)) ans=max(ans,mid),L=mid+1;
        else R=mid-1;
    }
    return ans;
}
void reverse()
{
    int l,r; scanf("%d%d",&l,&r);l++;r++;
    if(l>r) swap(l,r);
    splita(l,r); int g=ca[ca[rt1][1]][0];
    rev[g]^=1; pushdown(g);
    updata1(faa[g]); updata1(rt1);
}
int main()
{
 //   freopen("read.in","r",stdin);
    n=read();m=read();
    for(int i=2;i<=n+1;i++) scanf("%d",&A[i]);A[1]=0;A[n+2]=0; lsd1=n+2;
    for(int i=2;i<=m+1;i++) scanf("%d",&B[i]);B[1]=0;B[m+2]=0; lsd2=m+2;
    for(int i=1;i<=4;i++) scanf("%d",&k),Q+=k;
    pows[0]=1;for(int i=1;i<=max(n,m)+3;i++)  pows[i]=pows[i-1]*xx;
    rt1=built1(0,1,n+2);rt2=built2(0,1,m+2);
    for(int i=1;i<=Q;i++)
    {
        char com[10];
        scanf("%s",com);
        if(com[0]==‘Q‘) printf("%d\n",query());
        else if(com[0]==‘D‘) erase();
        else if(com[0]==‘I‘) insert();
        else if(com[0]==‘R‘) reverse();
    }  
    return 0;
}