bzoj 1014: [JSOI2008]火星人prefix

用treap记录前缀哈希值，二分求最大值

#include<bits/stdc++.h>
using namespace std;


#define maxn 100005
//

const int P1=1e7+7;
const int B1=194317;

int Pow1[ 110000 ];
int Pow2[ 110000 ];

struct TreeNode {
    TreeNode *L,*R,*fa;
    int siz;
    int pri;
    int ch;
    int has;
};

TreeNode nodes[maxn*3];
int cnt_node;

TreeNode* create(int ch,int pri){
++cnt_node;
TreeNode* tmp=&nodes[ cnt_node ];
tmp->L=NULL;
tmp->R=NULL;
tmp->fa=NULL;
tmp->siz=1;
tmp->pri=pri;
tmp->ch=ch;
tmp->has=ch;
return tmp;
}



    void update(TreeNode* now)
    {
        now->siz=1;
        now->has=now->ch;
        if ( now->L !=NULL )
        {
            now->siz+=now->L->siz;
            now->has=(now->ch+1ll*now->L->has*B1 )%P1;
            now->L->fa=now;
        }
        if ( now->R !=NULL )
        {
            now->siz+=now->R->siz;
            now->has=(1ll*now->has*Pow1[ now->R->siz ]%P1+1ll*now->R->has)%P1;
            now->R->fa=now;
        }
    }

    void out(TreeNode* now){
        if ( now==NULL )    return ;
        out(now->L);
        printf("ch=%d siz=%d hash=%d pri=%d\n",now->ch,now->siz,now->has,now->pri);
        out(now->R);
    }

    TreeNode* get_kth(TreeNode *now,int k){
        if ( now->siz<k )    return NULL;
        while ( now!=NULL )
            {
                if (now->L!=NULL )
                    if ( now->L->siz >= k )
                    {
                        now=now->L;
                        continue;
                    }
                    else
                        k-=now->L->siz;
                if ( 1 >= k )
                    return now;
                k-=1;
                now=now->R;
            }
        return now;
    }



    TreeNode* Merge(TreeNode* A , TreeNode* B) {
        if (A == NULL)
            return B;
        if (B == NULL)
            return A;
        if (A->pri < B->pri) {
            A->R = Merge(A->R, B);
            update(A);  update(B);
            return A;
        } else {
            B->L = Merge(A, B->L);
            update(A);  update(B);
            return B;
        }
    }

    pair<TreeNode*, TreeNode*> split(TreeNode* now, int key) {
        if ( key==0 )
            return make_pair((TreeNode*)NULL,now);
        pair<TreeNode*, TreeNode*> tmp;
        if (now == NULL) {
            tmp = make_pair( (TreeNode* )NULL, (TreeNode* )NULL);
            return tmp;
        }
        if ( ( now->L!=NULL ) && (key <= now->L->siz) )
        {
            tmp = split(now->L, key);
            now->L = tmp.second;
            tmp.second = now;
        } else {
            if ( now->L != NULL )
                key-=now->L->siz;
            key--;
            tmp = split(now->R, key);
            now->R = tmp.first;
            tmp.first = now;
        }
        update(now);
        return tmp;
    }

inline void read(int &x){
    char ch;
    bool flag = false;
    for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true;
    for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    x = flag ? -x : x;
}

const int P=1e7+7;

int get_rand(){
return 1ll*rand()*rand()%P;
}

const int MAXN=200100;

int n,m;
char s[ MAXN ];
char op[ MAXN ];
char t[ MAXN ];
TreeNode* root;

void build(int l,int r){
if ( l>r )  return ;
int mid=(l+r)/2;
build(l,mid-1);
TreeNode* tmp=create(s[mid]-'a'+1,get_rand());
root=Merge(root,tmp);
build(mid+1,r);
}

    int get_kth_has(TreeNode *now,int k){
        if ( k==0 ) return 0;
        if ( now->siz<k )    return 0;
        long long ans=0;
        while ( now!=NULL )
            {
                if (now->L!=NULL )
                    if ( now->L->siz >= k )
                    {
                        now=now->L;
                        continue;
                    }
                    else
                        {
                            k-=now->L->siz;
                            ans=(ans+1ll*Pow1[k]*now->L->has%P1)%P1;
                        }
                k--;
                ans=(ans+1ll*now->ch*Pow1[k]%P1)%P1;
                if ( 0 >= k )
                    return ans;
                now=now->R;
            }
        return ans;
    }

int get_has(int has_st,int ed,int len){
long long has=get_kth_has(root,ed);
has=(has-1ll*has_st*Pow1[len]%P1 )%P1;
if ( has<0 )
    has=has+P1;
return has;
}


int sum=0;

int get_ans(int x,int y){
int l=1,r=root->siz-max(x,y)+1;
int ans=0;
int has_x=get_kth_has(root,x-1);
int has_y=get_kth_has(root,y-1);

while ( l<=r )
    {
        int mid=(l+r)/2;
        if ( get_has(has_x,x+mid-1,mid) == get_has(has_y,y+mid-1,mid) )
            {
                l=mid+1;
                ans=mid;
            }
        else
            r=mid-1;
    }
return ans;
}

inline void write(int x) {
    static const int maxlen = 100;
    static char s[maxlen];
    if (x < 0) {   putchar('-'); x = -x;}
    if (!x) { putchar('0'); return; }
    int len = 0; for (; x; x /= 10) s[len++] = x % 10 + '0';
    for (int i = len - 1; i >= 0; --i) putchar(s[i]);
}


int dfs(TreeNode* now){
int deep=0;
if ( now->L !=NULL )    deep=max(deep,dfs(now->L)+1);
if ( now->R !=NULL )    deep=max(deep,dfs(now->R)+1);
return deep;
}


int main(){
    Pow1[0]=1;
    Pow2[0]=1;
    for (int i=1;i<=1e5;i++)
        Pow1[i]=1ll*Pow1[i-1]*B1%P1;
    scanf("%s",s);
    n=strlen(s);
    root=NULL;
    build(0,n-1);
    read(m);
    for (int i=1;i<=m;i++)
        {
            scanf("%s",op);
            if ( op[0]=='R' )
                {
                    int x;read(x);
                    scanf("%s",t);
                    TreeNode* tmp=get_kth(root,x);
                    tmp->ch=t[0]-'a'+1;
                    while ( tmp!=NULL )
                        {
                            update(tmp);
                            tmp=tmp->fa;
                        }
                }
            else
            if ( op[0]=='I' )
                {
                    int x;read(x);
                    scanf("%s",t);
                    TreeNode* tmp;
                    tmp=create(t[0]-'a'+1,get_rand());
                    if ( x==0 )
                        root=Merge(tmp,root);
                    else
                    {
                        TreeNode* now=get_kth(root,x);
                        now->R=Merge(tmp,now->R);
                        while ( now!=NULL )
                            {
                                update(now);
                                now=now->fa;
                            }
                    }
                }
            else
                {
                    int x,y;
                    read(x);read(y);
                    write(get_ans(x,y));
                    puts("");
                }
        }
    return 0;
}