【BZOJ1014】【JSOI2008】火星人

支持插入修改什么的序列操作显然是Splay啊。

每个结点维护一下子树hash值即可。

// <1014.cpp> - 05/19/16 17:36:52
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
typedef unsigned long long ull;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100010;
const int INF=1e9;
const int seed=31;
int n,root;
char ch[MAXN];
ull h[MAXN],ha[MAXN];
int f[MAXN],s[MAXN][2];
int size[MAXN],val[MAXN];
inline void update(int x){
    int l=s[x][0],r=s[x][1];
    size[x]=size[l]+size[r]+1;
    ha[x]=ha[r]+val[x]*h[size[r]]+ha[l]*h[size[r]+1];
}
void build(int l,int r,int last){
    if(l>r)return;
    int m=(l+r)>>1;
    if(l==r)size[m]=1;
    else{
        build(l,m-1,m);
        build(m+1,r,m);
    }
    f[m]=last;s[last][m>last]=m;
    update(m);
}
int src(int now,int k){
    int l=s[now][0],r=s[now][1];
    if(size[l]+1==k)return now;
    if(size[l]>=k)return src(l,k);
    return src(r,k-size[l]-1);
}
inline void R(int a,int &k){
    int p=f[a],g=f[p];
    bool l=a==s[p][1],r=!l;
    if(p==k)k=a;
    else s[g][s[g][1]==p]=a;f[a]=g;
    f[s[a][r]]=p;s[p][l]=s[a][r];
    f[p]=a;s[a][r]=p;
    update(p);update(a);
}
inline void splay(int a,int &k){
    while(a!=k){
        int p=f[a];
        if(p!=k){
            if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k);
            else R(p,k);
        }
        R(a,k);
    }
}
inline void split(int l,int r){
    splay(src(root,l),root);
    splay(src(root,r+2),s[root][1]);
}
inline ull geth(int l,int r){split(l,r);return ha[s[s[root][1]][0]];}
inline int ask(int x,int y){
    int l=0,r=n-2-max(x,y);
    while(l<r){
        int m=(l+r+1)>>1;
        if(geth(x,x+m)==geth(y,y+m))l=m;
        else r=m-1;
    }
    return l+(geth(x,x+l)==geth(y,y+l));
}
inline void change(int x,char c){
    splay(src(root,x+1),root);
    val[root]=c-'a'+1;
    update(root);
}
inline void insert(int x,char c){
    val[++n]=c-'a'+1;
    split(x+1,x);
    s[s[root][1]][0]=n;
    f[n]=s[root][1];
    update(n);
    update(f[n]);
    update(root);
}
int main(){
    scanf("%s",ch+1);
    n=strlen(ch+1);
    h[0]=1;
    for(int i=1;i<MAXN;i++)h[i]=h[i-1]*seed;
    for(int i=1;i<=n;i++)val[i+1]=ch[i]-'a'+1;
    val[1]=val[n+2]=0;
    build(1,n+2,0);
    root=(n+3)>>1;
    n=n+2;
    int m=gi();
    while(m--){
        scanf("%s",ch);
        if(ch[0]=='Q')printf("%d\n",ask(gi(),gi()));
        else{
            int x=gi();scanf("%s",ch+1);
            if(ch[0]=='R')change(x,ch[1]);
            else insert(x,ch[1]);
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// <1014.cpp> - 05/19/16 17:36:52

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

typedef unsigned long long ull;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100010;

const int INF=1e9;

const int seed=31;

int n,root;

char ch[MAXN];

ull h[MAXN],ha[MAXN];

int f[MAXN],s[MAXN][2];

int size[MAXN],val[MAXN];

inline void update(int x){

int l=s[x][0],r=s[x][1];

size[x]=size[l]+size[r]+1;

ha[x]=ha[r]+val[x]*h[size[r]]+ha[l]*h[size[r]+1];

}

void build(int l,int r,int last){

if(l>r)return;

int m=(l+r)>>1;

if(l==r)size[m]=1;

else{

build(l,m-1,m);

build(m+1,r,m);

}

f[m]=last;s[last][m>last]=m;

update(m);

}

int src(int now,int k){

int l=s[now][0],r=s[now][1];

if(size[l]+1==k)return now;

if(size[l]>=k)return src(l,k);

return src(r,k-size[l]-1);

}

inline void R(int a,int &k){

int p=f[a],g=f[p];

bool l=a==s[p][1],r=!l;

if(p==k)k=a;

else s[g][s[g][1]==p]=a;f[a]=g;

f[s[a][r]]=p;s[p][l]=s[a][r];

f[p]=a;s[a][r]=p;

update(p);update(a);

}

inline void splay(int a,int &k){

while(a!=k){

int p=f[a];

if(p!=k){

if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k);

else R(p,k);

}

R(a,k);

}

inline void split(int l,int r){

splay(src(root,l),root);

splay(src(root,r+2),s[root][1]);

}

inline ull geth(int l,int r){split(l,r);return ha[s[s[root][1]][0]];}

inline int ask(int x,int y){

int l=0,r=n-2-max(x,y);

while(l<r){

int m=(l+r+1)>>1;

if(geth(x,x+m)==geth(y,y+m))l=m;

else r=m-1;

}

return l+(geth(x,x+l)==geth(y,y+l));

}

inline void change(int x,char c){

splay(src(root,x+1),root);

val[root]=c-'a'+1;

update(root);

}

inline void insert(int x,char c){

val[++n]=c-'a'+1;

split(x+1,x);

s[s[root][1]][0]=n;

f[n]=s[root][1];

update(n);

update(f[n]);

update(root);

}

int main(){

scanf("%s",ch+1);

n=strlen(ch+1);

h[0]=1;

for(int i=1;i<MAXN;i++)h[i]=h[i-1]*seed;

for(int i=1;i<=n;i++)val[i+1]=ch[i]-'a'+1;

val[1]=val[n+2]=0;

build(1,n+2,0);

root=(n+3)>>1;

n=n+2;

int m=gi();

while(m--){

scanf("%s",ch);

if(ch[0]=='Q')printf("%d\n",ask(gi(),gi()));

else{

int x=gi();scanf("%s",ch+1);

if(ch[0]=='R')change(x,ch[1]);

else insert(x,ch[1]);

}

return 0;

}