火星人prefix bzoj-1014 JSOI-2004
题目大意：给定一个字符串，支持三种操作：1.查询；两个后缀之间的$LCP$；2.单点修改；3.插入一个字符。
注释：$1\le n\le 10^5$，$1\le m\le 1.5\cdot 10^5$。
想法：
第一眼就是后缀数组，但是发现有单点插入操作果断$pass$。
一个序列支持单点插入肯定最少是个平衡树。
又发现$log^2n$好像能过，我们就对序列建立非旋转$Treap$然后维护子树$hash$值。
每一次查询的时候二分，然后撕出区间暴力验证即可。
时间复杂度$O(mlog^2n)$。
Code：
#include <bits/stdc++.h>
#define N 100010
using namespace std;
typedef unsigned int ull;
const ull base = 97 ;
int root,cnt; char s[N];
ull B[1000010];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
char buf[100000],*p1,*p2;
inline int rd()
{
register int x=0;register char c=nc();
while(c<'0'||c>'9')c=nc();
while(c>='0'&&c<='9')x=((x+(x<<2))<<1)+(c^48),c=nc();
return x;
}
struct Node
{
int ls,rs,size,key;
ull sum,val;
}a[N<<1];
struct par {int x,y;};
inline void pushup(int x)
{
int ls=a[x].ls,rs=a[x].rs;
a[x].sum=a[x].val; a[x].size=1;
if(ls) a[x].sum-=a[x].val,a[x].sum+=a[ls].sum+a[x].val*B[a[ls].size],a[x].size+=a[ls].size;
if(rs) a[x].sum+=a[rs].sum*B[a[ls].size+1],a[x].size+=a[rs].size;
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(a[x].key>a[y].key)
{
a[x].rs=merge(a[x].rs,y); pushup(x);
return x;
}
else
{
a[y].ls=merge(x,a[y].ls); pushup(y);
return y;
}
}
par split(int x,int k)
{
if(!k) return (par){0,x};
int ls=a[x].ls,rs=a[x].rs;
if(k==a[ls].size)
{
a[x].ls=0; pushup(x);
return (par){ls,x};
}
else if(k==a[ls].size+1)
{
a[x].rs=0; pushup(x);
return (par){x,rs};
}
else if(k<a[ls].size)
{
par t=split(ls,k);
a[x].ls=t.y; pushup(x);
return (par){t.x,x};
}
else
{
par t=split(rs,k-a[ls].size-1);
a[x].rs=t.x; pushup(x);
return (par){x,t.y};
}
}
inline int newnode(ull val)
{
int x=++cnt;
a[x].ls=a[x].rs=0; a[x].size=1;
a[x].sum=a[x].val=val; a[x].key=rand()*rand();
return x;
}
void insert(int x,ull val)
{
par t=split(root,x);
root=merge(t.x,merge(newnode(val),t.y));
}
ull query(int x,int k)
{
par t1=split(root,x-1),t2=split(t1.y,k);
ull re=a[t2.x].sum;
root=merge(t1.x,merge(t2.x,t2.y));
return re;
}
void update(int x,ull y)
{
par t1=split(root,x-1),t2=split(t1.y,1);
root=merge(t1.x,merge(newnode(y),t2.y));
}
void output(int x)
{
int ls=a[x].ls,rs=a[x].rs;
if(ls) output(ls);
printf("%lld ",a[x].val);
if(rs) output(rs);
}
int build(int l,int r)
{
if(l==r) return newnode(s[l]-'a'+1);
int mid=(l+r)>>1;
return merge(build(l,mid),build(mid+1,r));
}
int main()
{
srand(20021214);
B[0]=1;
for(int i=1;i<=1000000;i++) B[i]=B[i-1]*base;
scanf("%s",s+1); int n=strlen(s+1);
root=build(1,n);
int m=rd(); while(m--)
{
char opt=nc(); while(opt!='Q'&&opt!='R'&&opt!='I')opt=nc(); int x=rd();
if(opt=='Q')
{
int y=rd();
int r=min(n-x+1,n-y+1)+1,l=0;
// printf("%d %d\n",x,y);
while(l<r)
{
int mid=(l+r)>>1;
// printf("%d %lld %lld\n",mid,query(x,mid),query(y,mid));
if(query(x,mid)==query(y,mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
// printf("djhdjhfjhfgjuhdfgiodfg=%d\n",query(x,5)==query(y,5));
// r--;
// int d,p=0;
// for(d=1;d<=r&&query(x,d)==query(y,d);d<<=1) ;
// for(d>>=1;d;d>>=1) if(p+d<=r&&query(x,p+d)==query(y,p+d)) p+=d;
// // printf("djhdjhfjhfgjuhdfgiodfg=%d\n",query(x,5)==query(y,5));
// printf("%d\n",p);
}
else if(opt=='R')
{
char d=nc();while(d<'a'&&d>'z')d=nc(); ull val=d-'a'+1;
update(x,val);
}
else
{
n++;
char d=nc();while(d<'a'&&d>'z')d=nc(); ull val=d-'a'+1;
insert(x,val);
}
}
return 0;
}
小结：卧槽这题卡常，用特判+读入优化+非旋转$Treap$的$O(n)$建树才卡过去。