真的字符串

C++11(clang++ 3.9) 解法, 执行用时: 1245ms, 内存消耗: 177120K, 提交时间: 2020-06-11 09:06:53

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 800000
#define Q 3000000
using namespace std;
int n,fg;char op[10],s[Q+5];
class LinkCutTree
{
	private:
		#define PU(x) (O[x].Sz=O[x].ISz+O[O[x].S[0]].Sz+O[O[x].S[1]].Sz+O[x].T)
		#define IR(x) (O[O[x].F].S[0]^x&&O[O[x].F].S[1]^x)
		#define Wh(x) (O[O[x].F].S[1]==x)
		#define Co(x,y,d) (O[O[x].F=y].S[d]=x)
		#define PD(x) O[x].R&&(Re(O[x].S[0]),Re(O[x].S[1]),O[x].R=0)
		#define Re(x) (swap(O[x].S[0],O[x].S[1]),O[x].R^=1)
		#define MR(x) (Ac(x),S(x),Re(x))
		int St[N<<1];struct node {int T,Sz,ISz,R,F,S[2];}O[N<<1];
		I void Ro(RI x)
		{
			RI f=O[x].F,p=O[f].F,d=Wh(x);!IR(f)&&(O[p].S[Wh(f)]=x),
			O[x].F=p,Co(O[x].S[d^1],f,d),Co(f,x,d^1),PU(f),PU(x);
		}
		I void S(RI x)
		{
			RI f=x,T=0;W(St[++T]=f,!IR(f)) f=O[f].F;W(T) PD(St[T]),--T;
			W(!IR(x)) f=O[x].F,!IR(f)&&(Ro(Wh(x)^Wh(f)?x:f),0),Ro(x);
		}
		I void Ac(RI x)
		{
			for(RI y=0;x;x=O[y=x].F) S(x),
				O[x].ISz+=O[O[x].S[1]].Sz-O[y].Sz,O[x].S[1]=y,PU(x);
		}
	public:
		I void Init(CI x) {O[x].Sz=O[x].T=1;}
		I void Link(CI x,CI y) {MR(x),MR(y),O[O[y].F=x].ISz+=O[y].Sz,O[x].Sz+=O[y].Sz;}
		I void Cut(CI x,CI y) {MR(x),Ac(y),S(x),O[x].Sz-=O[y].Sz,O[x].S[1]=O[y].F=0;}
		I void Del(CI x) {MR(x),O[x].T=0,--O[x].Sz;}
		I int Qry(CI f,CI x) {return MR(f),Ac(x),S(f),O[x].Sz;}
}LCT;
class SuffixAutomation
{
	private:
		int Nt,lst,T,S[N+5];struct node {int L,F,S[30];}O[N<<1];
	public:
		I SuffixAutomation() {S[T=1]=Nt=lst=1;}
		I void Ins(CI x)
		{
			RI p=lst,now=lst=++Nt;O[S[++T]=now].L=O[p].L+1,LCT.Init(now);
			W(p&&!O[p].S[x]) O[p].S[x]=now,p=O[p].F;if(!p) return LCT.Link(O[now].F=1,now);
			RI q=O[p].S[x];if(O[p].L+1==O[q].L) return LCT.Link(O[now].F=q,now);
			RI k=++Nt;(O[k]=O[q]).L=O[p].L+1,O[now].F=O[q].F=k,
			LCT.Cut(O[k].F,q),LCT.Link(O[k].F,k),LCT.Link(k,now),LCT.Link(k,q);
			W(p&&O[p].S[x]==q) O[p].S[x]=k,p=O[p].F;
		}
		I int Qry(char *s)
		{
			RI p=1;for(RI i=1;i<=n;++i) if(!(p=O[p].S[s[i]&31])) return 0;
			return LCT.Qry(O[p].F,p);
		}
		I void Del(CI t) {T-=t,lst=fg?0:S[T];for(RI i=1;i<=t;++i) LCT.Del(S[T+i]);}
}S;
I void T(char *s,RI p) {for(RI i=1;i<=n;++i) swap(s[i],s[(p=(p*131+i-1)%n)+1]);}
int main()
{
	RI Qt,i;for(scanf("%d%s",&Qt,s+1),n=strlen(s+1),i=1;i<=n;++i) S.Ins(s[i]&31);
	RI t,p=0;fg=Qt<=50000;W(Qt--) switch(scanf("%s",op),op[0])
	{
		case 'Q':scanf("%s",s+1),n=strlen(s+1),T(s,p),printf("%d\n",t=S.Qry(s)),p^=t;break;
		case 'A':scanf("%s",s+1),n=strlen(s+1),T(s,p);for(i=1;i<=n;++i) S.Ins(s[i]&31);break;
		case 'D':scanf("%d",&t),S.Del(t);break;
	}return 0;
}

C++14(g++5.4) 解法, 执行用时: 982ms, 内存消耗: 12552K, 提交时间: 2019-07-12 16:19:03

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
const int N = 3e6+5;
const double Alpha = 0.7;
int mask,n,q,l,rt,tot,ls[N],rs[N],sz[N],s[N],top,ans;
char str[N],opt[10],que[N];double a[N];
 
void dfs(int &x){
    if (!x) return;
    dfs(ls[x]);s[++top]=x;dfs(rs[x]);x=0;
}
void build(int &x,int L,int R,double l,double r){
    if (L>R) {x=0;return;}
    int MID=L+R>>1;double mid=(l+r)/2.0;
    a[x=s[MID]]=mid;sz[x]=R-L+1;
    build(ls[x],L,MID-1,l,mid);
    build(rs[x],MID+1,R,mid,r);
}
void rebuild(int &x,double l,double r){
    top=0;dfs(x);build(x,1,top,l,r);
}
void insert(int &x,int y,double l,double r,int f){
    double mid=(l+r)/2.0;
    if (!x) {x=y,ls[x]=rs[x]=0,a[x]=mid,sz[x]=1;return;}
    int fg=f;++sz[x];
    if (str[y]<str[x]||(str[y]==str[x]&&a[y-1]<a[x-1])){
        fg|=(Alpha*sz[x]<=sz[ls[x]]+1);
        insert(ls[x],y,l,a[x],fg);
    }else{
        fg|=(Alpha*sz[x]<=sz[rs[x]]+1);
        insert(rs[x],y,a[x],r,fg);
    }
    if (fg&&!f) rebuild(x,l,r);
}
#define upt(x) sz[x]=sz[ls[x]]+sz[rs[x]]+1
void merge(int x,int y,int &p){
    if (!x||!y) {p=x|y;return;}
    if (sz[x]>sz[y]) merge(rs[x],y,rs[x]),upt(x),p=x;
    else merge(x,ls[y],ls[y]),upt(y),p=y;
}
void del(int &x,int y){
    if (x^y) --sz[x],del(a[y]<a[x]?ls[x]:rs[x],y);
    else merge(ls[x],rs[x],x);
}
void readin(){
    scanf("%s",que);l=strlen(que);
    for (int i=0,tmp=mask;i<l;++i)
        tmp=(tmp*131+i)%l,swap(que[i],que[tmp]);
}
int query(int x){
    if (!x) return 0;int c=0;
    for (int i=0;i<=l;++i)
        if (que[i]^str[x-i]) {c=que[i]>str[x-i];break;}
    return c?sz[ls[x]]+1+query(rs[x]):query(ls[x]);
}
int main(){
//  freopen("1.in","r",stdin);
//  freopen("zsy.out","w",stdout);
    q=gi();scanf("%s",str+1);n=strlen(str+1);
    for (int i=1;i<=n;++i) insert(rt,i,0,1e9,0);
    while (q--){
        scanf("%s",opt);
        if (opt[0]=='Q'){
            readin();reverse(que,que+l);
            ans=-query(rt);que[l]='Z'+1;ans+=query(rt);
            printf("%d\n",ans);mask^=ans;
        }
        if (opt[0]=='A'){
            readin();
            for (int i=1;i<=l;++i) str[n+i]=que[i-1],insert(rt,n+i,0,1e9,0);
            n+=l;
        }
        if (opt[0]=='D'){
            l=gi();n-=l;
            for (int i=1;i<=l;++i) del(rt,n+i);
        }
    }
    return 0;
}

详情