这个题目我成功爆零，\(\color{blue}{TTTTTLE}\)了全部的点……我可真棒啊……
\(\color{red}{Description}\)
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：\(madamimadam\)，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数\(LCQ(x,y)\)，表示：该字符串中第x个字符开始的字串，与该字符串中第\(y\)个字符开始的字串
，两个字串的公共前缀的长度。比方说，\(LCQ(1, 7) = 5\), \(LCQ(2, 10) = 1, LCQ(4, 7) = 0\) 在研究\(LCQ\)函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出\(LCQ\)函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取\(LCQ\)函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取\(LCQ\)函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取\(LCQ\)函数的值。
\(\color{red}{Input}\)
第一行给出初始的字符串。第二行是一个非负整数\(M\)，表示操作的个数。接下来的\(M\)行，每行描述一个操作。操
作有3种，如下所示
\(1\)、询问。语法：\(Qxy\)，\(x,y\)均为正整数。功能：计算\(LCQ(x,y)\)限制：1<=x,y<=当前字符串长度。
\(2\)、修改。语法：\(Rxd\)，\(x\)是正整数，\(d\)是字符。功能：将字符串中第\(x\)个数修改为字符\(d\)。限制：\(x\)不超过当前字
符串长度。
\(3\)、插入：语法：\(Ixd\)，\(x\)是非负整数，\(d\)是字符。功能：在字符串第\(x\)个字符之后插入字符d，如果\(x=0\)，则在字
符串开头插入。限制：\(x\)不超过当前字符串长度
\(\color{red}{Output}\)
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
\(\color{red}{Sample \ \ ?Input}\)
madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11
\(\color{red}{Sample \ \ ?Output}\)
5
1
0
2
1
\(\color{red}{HINT}\)
1、所有字符串自始至终都只有小写字母构成。
2、\(M<=150,000\)
3、字符串长度L自始至终都满足L<=100,000
4、询问操作的个数不超过10,000个。
对于第1，2个数据，字符串长度自始至终都不超过1,000
对于第3，4，5个数据，没有插入操作。
\(\color{purple}{Half-solution}\)
咳，对比着记录吧，我暂时只会\(TLE\)版本的暴力，先贴上来记录我光辉的历史。
插入就是插入，修改就是修改，但是因为事实上我当时\(Splay\)只学了一半，所以现在对区间\(Splay\)无所适从\(OTZ\)……
嗯，那么查询的话，就是不断查询自己的父节点，或者右子节点，但是由于你\(Splay\)的话会使得序列无序，所以并不可做。
那么事实上你看，这其实是一个会\(WA\)但是先\(TLE\)了的算法。
哈哈哈我还调试了半天。
真有趣。
#include<iostream>#include<cstdio>#define MAXN 250001#define il inline using namespace std;struct chars{ ???unsigned int son[2],f,sub; ???char v;}s[MAXN];char t,base[MAXN],cc;unsigned int k,res;unsigned int xx,yy,m,a,b,i,qwq,root,wz,now,fnow,ffnow;il bool w(unsigned int x){ ???return x==s[s[x].f].son[1];}il void push_up(unsigned int x){ ???if(x){ ???????s[x].sub=1; ???????if(s[x].son[1])s[x].sub+=s[s[x].son[1]].sub; ???????if(s[x].son[0])s[x].sub+=s[s[x].son[0]].sub; ???}}il void rotate(unsigned int x){ ???fnow=s[x].f,ffnow=s[fnow].f; ???bool ww=w(x); ???s[fnow].son[ww]=s[x].son[ww^1]; ???s[s[fnow].son[ww]].f=fnow; ???s[fnow].f=x; ???s[x].f=ffnow; ???s[x].son[ww^1]=fnow; ???if(ffnow){ ???????s[ffnow].son[s[ffnow].son[1]==fnow]=x; ???} ???push_up(fnow); ???push_up(x);}void splay(unsigned int x,unsigned int goal){ ???for(qwq;(qwq=s[x].f)!=goal;rotate(x)){ ???????if(s[qwq].f!=goal){ ???????????rotate(w(x)==w(qwq)?qwq:x); ???????} ???} ???if(goal==0){ ???????root=x; ???}}void insert(unsigned int pos,char c){ ???if(!wz){ ???????wz++; ???????root=wz; ???????s[wz].f=s[wz].son[1]=s[wz].son[0]=0; ???????s[wz].sub++; ???????s[wz].v=c; ???????return ; ???} ???if(!pos){ ???????wz++; ???????s[wz].son[1]=root,s[wz].v=c; ???????s[root].f=wz; ???????root=wz; ???????push_up(wz); ???????return ; ???} ???now=root; ???while(1){ ???????if(s[now].son[0]&&pos<=s[s[now].son[0]].sub) ???????now=s[now].son[0]; ???????else { ???????????unsigned int temp=(s[now].son[0]?s[s[now].son[0]].sub:0)+1; ???????????if(pos<=temp)break; ???????????pos-=temp; ???????????now=s[now].son[1]; ???????} ???} ???wz++; ???s[wz].son[1]=s[now].son[1]; ???s[s[now].son[1]].f=wz; ???s[now].son[1]=wz; ???s[wz].f=now; ???s[wz].v=c; ???push_up(wz); ???push_up(now); ???//splay(wz,0);}il void update(unsigned int pos,char c){ ???now=root; ???while(1){ ???????if(s[now].son[0]&&pos<=s[s[now].son[0]].sub) ???????now=s[now].son[0]; ???????else { ???????????unsigned int temp=(s[now].son[0]?s[s[now].son[0]].sub:0)+1; ???????????if(pos<=temp)break; ???????????pos-=temp; ???????????now=s[now].son[1]; ???????} ???} ???s[now].v=c;// ???splay(now,0);}il unsigned int find(unsigned int sx,unsigned int sy){ ???xx=root,res=0,yy=root; ???while(1){ ???????if(s[xx].son[0]&&sx<=s[s[xx].son[0]].sub) ???????xx=s[xx].son[0]; ???????else { ???????????unsigned int temp=(s[xx].son[0]?s[s[xx].son[0]].sub:0)+1; ???????????if(sx<=temp)break; ???????????sx-=temp; ???????????xx=s[xx].son[1]; ???????} ???} ???while(1){ ???????if(s[yy].son[0]&&sy<=s[s[yy].son[0]].sub) ???????yy=s[yy].son[0]; ???????else { ???????????unsigned int temp=(s[yy].son[0]?s[s[yy].son[0]].sub:0)+1; ???????????if(sy<=temp)break; ???????????sy-=temp; ???????????yy=s[yy].son[1]; ???????} ???} ???while(1){ ???????if(s[yy].v==s[xx].v)res++; ???????yy=s[yy].son[1]; ???????xx=s[xx].son[1]; ???????if(!yy||!xx||s[yy].v!=s[xx].v){ ???????????return res; ???????} ???}}il unsigned int qread(){ ???k=0,cc=getchar(); ???while(!isdigit(cc)){ ???????cc=getchar(); ???} ???while(isdigit(cc)){ ???????k=(k<<1)+(k<<3)+cc-48; ???????cc=getchar(); ???} ???return k;}int main(){ ???scanf("%s",base); ???m=qread(); ???for(i=0;base[i];i++){ ???????insert(i,base[i]); ???} ???for(i=1;i<=m;i++){ ???????scanf("%c",&t); ???????if(t==‘I‘){ ???????????a=qread(); ???????????scanf("%c",&t); ???????????insert(a,t); ???????????continue; ???????} ???????else if(t==‘R‘){ ???????????a=qread(); ???????????scanf("%c",&t); ???????????update(a,t); ???????????continue; ??????????????????} ???????a=qread(); ???????b=qread(); ???????printf("%d\n",find(a,b)); ???} ???return 0;}以上已经被挂在了历史的耻辱柱上
[JSOI2008]火星人
原文地址：https://www.cnblogs.com/pks-t/p/9112776.html