题解 P4036 【[JSOI2008]火星人】

Dispwnl · 2018-05-07 21:34:55 · 题解

emmm。。。题意做法前面都说的很明白了

发现（也可能是我没找到）竟然没人用Fhq Treap做你们是不是看不起Treap

Fhq Treap支持单点插入，单点删除（修改时用），区间查询

还是很好写的我™还WA了这么多次

注意树上点要赋初值不然只有30分

用unsigned int似乎比int快了不止一点。。。似乎是处理负数费时间

代码：

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cstdlib>
# define LL unsigned int
using namespace std;
const int MAX=2e5+1;
int rt,tot,n,m;
string A;
LL ha[MAX];
struct Fhq_Treap{
    int pos[MAX],siz[MAX],Ch[MAX];
    LL w[MAX];
    int son[MAX][2];
    void pus(int x)
    {
        siz[x]=siz[son[x][1]]+siz[son[x][0]]+1;
        w[x]=w[son[x][0]]*ha[siz[son[x][1]]+1]+ha[siz[son[x][1]]]*Ch[x]+w[son[x][1]];
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        if(pos[x]<pos[y])
        {
            son[x][1]=merge(son[x][1],y);
            pus(x);
            return x;
        }
        else
        {
            son[y][0]=merge(x,son[y][0]);
            pus(y);
            return y;
        }
    }
    void split(int i,int k,int &a,int &b)
    {
        if(!i) a=b=0;
        else
        {
            if(k<=siz[son[i][0]])
            b=i,split(son[i][0],k,a,son[i][0]);
            else a=i,split(son[i][1],k-siz[son[i][0]]-1,son[i][1],b);
            pus(i);
        }
    }
    void ins(int x,char ch)
    {
        int a,b;
        split(rt,x,a,b);
        w[++tot]=Ch[tot]=ch-'a'+1,siz[tot]=1,pos[tot]=rand();
        rt=merge(merge(a,tot),b);
    }
    void cut(int x)
    {
        int a,b,c;
        split(rt,x,a,c);
        split(a,x-1,a,b);
        b=merge(son[b][0],son[b][1]);
        rt=merge(merge(a,b),c);
    }
    LL ask(int l,int r)
    {
        int L=r-l+1;
        int a,b,c,d;
        split(rt,l-1,a,b);
        split(b,L,c,d);
        LL ans=w[c];
        rt=merge(a,merge(c,d));
        return ans;
    }
    bool look(int x,int y,int mid)
    {
        LL ans1=ask(x,x+mid-1),ans2=ask(y,y+mid-1);
        return ans1==ans2;
    }
}Tree;
string Read()
{
    string a=" ";
    char ch=getchar();
    for(;ch>'z'||ch<'a';ch=getchar());
    for(;ch<='z'&&ch>='a';a+=ch,ch=getchar());
    return a;
}
char read_char()
{
    char ch=getchar();
    for(;ch>'z'||ch<'A';ch=getchar());
    return ch;
}
int read()
{
    int x=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
    return x;
}
int main()
{
    A=Read(),n=A.length()-1,m=read();
    ha[0]=1;
    for(int i=1;i<MAX;++i)
      ha[i]=ha[i-1]*27;
    for(int i=1;i<=n;++i)
      Tree.ins(i,A[i]);
    for(int i=1;i<=m;++i)
      {
        char op=read_char();
        if(op=='Q')
        {
            int x=read(),y=read();
            int l=1,r=min(n-x,n-y)+1,ans=0;
            while(l<=r)
            {
                int mid=(l+r>>1);
                if(Tree.look(x,y,mid)) l=mid+1,ans=mid;
                else r=mid-1;
            }
            printf("%d\n",ans);
        }
        else if(op=='R')
        {
            int x=read();
            Tree.cut(x),Tree.ins(x-1,read_char());
        }
        else if(op=='I')
        {
            int x=read();
            ++n,Tree.ins(x,read_char());
        }
      }
    return 0;
}