显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int TYPE;
const int maxn=100010;
const TYPE H=10000007;
const ll e=(1ll<<61);
int son[maxn][2],hkey[maxn],Rt,N=0,goat=0;
TYPE hash[maxn],POW[maxn];
ll tag[maxn],ans=0,nowl,nowr;
char ch[maxn],s[maxn];
#define L(x) son[x][0]
#define R(x) son[x][1]
void rebuild(int x,ll l,ll r){
if(!x)return;
ll mid=(l+r)/2;
tag[x]=mid;
rebuild(L(x),l,mid);rebuild(R(x),mid,r);
}
int rotate(int x,int k,ll l,ll r){
int y=son[x][k^1];
son[x][k^1]=son[y][k];
son[y][k]=x;
rebuild(y,l,r);
return y;
}
int rotate(int x,int k){
int y=son[x][k^1];
son[x][k^1]=son[y][k];
son[y][k]=x;
return y;
}
bool dcmp(int x,int y){
return (s[x]<s[y]||(s[x]==s[y]&&tag[x-1]<tag[y-1]));
}
bool check(int x,int y,int mid){
return (hash[x]-hash[x-mid]*POW[mid])==(hash[y]-hash[y-mid]*POW[mid]);
}
int LCP(int x,int y){
int l=1,r=min(x,y),maxx=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(x,y,mid)){
l=mid+1;maxx=max(maxx,mid);
}
else r=mid-1;
}
return maxx;
}
int query_pre(int x){
int now=Rt,id=0;
while(now){
if(dcmp(now,x)){
if(!id||tag[now]>tag[id])id=now;
now=R(now);
}
else now=L(now);
}
return id;
}
int query_scn(int x){
int now=Rt,id=0;
while(now){
if(dcmp(x,now)){
if(!id||tag[now]<tag[id])id=now;
now=L(now);
}
else now=R(now);
}
return id;
}
int erase(int rt,int x,ll l,ll r){
ll mid=(l+r)/2;
if(rt==x){
if(!L(rt)){
rebuild(R(rt),l,r);
return R(rt);
}
if(!R(rt)){
rebuild(L(rt),l,r);
return L(rt);
}
if(hkey[L(rt)]<hkey[R(rt)])rt=rotate(rt,1),R(rt)=erase(R(rt),x,mid,r);
else rt=rotate(rt,0),L(rt)=erase(L(rt),x,l,mid);
goat=rt;nowl=l;nowr=r;
}
else if(tag[rt]<tag[x])R(rt)=erase(R(rt),x,mid,r);
else L(rt)=erase(L(rt),x,l,mid);
return rt;
}
void insert(int &rt,int x,ll l,ll r){
if(!rt){
rt=x;tag[x]=(l+r)/2;L(rt)=R(rt)=0;hkey[rt]=rand()%10000000+1;
return;
}
ll mid=(l+r)/2;
if(dcmp(x,rt))insert(L(rt),x,l,mid);
else insert(R(rt),x,mid,r);
if(L(rt)&&hkey[L(rt)]<hkey[rt])rt=rotate(rt,1,l,r);
else if(R(rt)&&hkey[R(rt)]<hkey[rt])rt=rotate(rt,0,l,r);
}
void check(){
cout<<"root"<<Rt<<endl;
for(int i=1;i<=N;i++)cout<<i<<" "<<tag[i]<<" "<<L(i)<<" "<<R(i)<<endl;
}
void Erase(int x){
int pre=query_pre(x),scn=query_scn(x);
int h1=0,h2=0;
if(pre)h1=LCP(pre,x);if(scn)h2=LCP(scn,x);
ans-=(ll)x-max(h1,h2);
goat=0;
Rt=erase(Rt,x,0,e);
if(goat)rebuild(goat,nowl,nowr);
printf("%lld\n",ans);
}
void Add(int x,char a){
s[x]=a;
hash[x]=hash[x-1]*H+a-'a';
int pre=query_pre(x),scn=query_scn(x);
int h1=0,h2=0;
if(pre)h1=LCP(pre,x);if(scn)h2=LCP(scn,x);
ans+=(ll)x-max(h1,h2);
insert(Rt,x,0,e);
printf("%lld\n",ans);
}
int main(){
srand(121212);
freopen("hahaha.in","r",stdin);freopen("hahaha.out","w",stdout);
int M;
scanf("%d",&M);
POW[0]=1;
for(int i=1;i<=M;i++)POW[i]=POW[i-1]*H;
scanf("%s",ch+1);
for(int i=1;i<=M;i++){
if(ch[i]=='-'){
Erase(N);
N--;
}
else Add(++N,ch[i]);
}
return 0;
}
半汪