很显然的后缀平衡树 一开始以为要可持久化 发现根本不用。。 treap的常数要死人啊？ 我好像T光光了？ 寄刀片寄刀片
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<map> #include<cmath> using namespace std; #define ld long long char Query[999101]; namespace Tree { struct Node { int no,rank,size,Rand; long long l,r; bool cs; long long val(){return l+r;} Node *lc,*rc; }*T[700000]; const int Max=300000; Node *Cache; int Cachetot; inline Node *New(){if(!Cachetot)Cache=new Node[Cachetot=Max];return Cache+(--Cachetot);} inline Node *New(int rand,int no,long long l,long long r){Node *K=New();K->cs=false;K->no=no;K->size=K->rank=1;K->Rand=rand;K->lc=K->rc=NULL;K->l=l,K->r=r;return K;} inline Node *New(Node *Old){Node *K=New();*K=*Old;return K;} char Con[700001]; int Cnt; Node *Cur; void Up(Node *a){a->size=(a->rank=(a->lc?a->lc->size:0)+1)+(a->rc?a->rc->size:0);} void Bg() { Con[0]='A'-1; Cur=T[0]=New(rand(),0,-1e15,1e15); } bool cmp(Node *a,Node *b) { return Con[a->no]^Con[b->no]?Con[a->no]<Con[b->no]:(T[a->no-1]->val())<(T[b->no-1]->val()); } void Modify(Node *N,long long l,long long r) { if(!N)return ; if((!N->cs)&&N->l==l&&N->r==r) return ; N->cs=false; N->l=l,N->r=r; Modify(N->lc,l,(l+r)/2); Modify(N->rc,(l+r)/2,r); } Node *Merge(Node *a,Node *b) { if(!a)return b; if(!b)return a; Node *R; if(a->Rand>b->Rand) R=a,R->rc=Merge(R->rc,b); else R=b,R->lc=Merge(a,R->lc); R->cs=true; Up(R); return R; } void Split(Node *Cur,Node *Op,Node *&Lc,Node *&Rc) { if(!Cur){Lc=Rc=NULL;return;} Cur->cs=true; if(cmp(Cur,Op)) { Lc=Cur; Split(Cur->rc,Op,Lc->rc,Rc); Up(Lc); return; } Rc=Cur; Split(Cur->lc,Op,Lc,Rc->lc); Up(Rc); } void insert(char k) { Con[++Cnt]=k; T[Cnt]=New(rand(),Cnt,-1,-1); Node *Lc,*Rc; Split(Cur,T[Cnt],Lc,Rc); Cur=Merge(Lc,T[Cnt]); Cur=Merge(Cur,Rc); Modify(Cur,-1e15,1e15); } Node *Del(Node *a) { if(!a)return NULL; a->cs=true; if(a->lc)return a->lc=Del(a->lc),Up(a),a; return a->rc; } void pop() { Node *Lc,*Rc; Split(Cur,T[Cnt],Lc,Rc); if(Rc==NULL) Cnt++,Cnt--; Rc=Del(Rc); Cur=Merge(Lc,Rc); Modify(Cur,-1e15,1e15); Cnt--; } int rank(Node *a,int Len) { if(!a)return 0; bool cp; for(int i=1;i<=Len;i++) if(Con[a->no-i+1]^Query[i]) { cp=Con[a->no-i+1]<Query[i]; break; } return (cp?a->rank+rank(a->rc,Len):(rank(a->lc,Len))); } int Qr(int Len) { Query[++Len]='A'-2; int p=rank(Cur,Len); Query[Len]='Z'+1; p=rank(Cur,Len)-p; return p; } } int L,mask; inline void Decode(int l) { int t=mask; for(int i=1;i<=l;i++){ t=(t*131+i-1)%l; swap(Query[i],Query[t+1]); } for(int i=1,j=l;i<j;i++,j--)swap(Query[i],Query[j]); } int main() { Tree::Bg(); freopen("self.in","r",stdin); freopen("self.out","w",stdout); int Q; scanf("%d",&Q); scanf("%s",Query); int Len=strlen(Query); for(int i=0;i<Len;i++)Tree::insert(Query[i]); while(Q--) { char c; do c=getchar();while(c!='A'&&c!='D'&&c!='Q'); if(c=='Q') { do c=getchar();while(c!=' '); int n; n=0; do c=getchar();while(c<'A'||c>'Z'); while(c<='Z'&&c>='A')Query[++n]=c,c=getchar(); Decode(n); L=Tree::Qr(n); mask^=L; printf("%d\n",L); } else if(c=='A') { do c=getchar();while(c!=' '); int n; n=0; do c=getchar();while(c<'A'||c>'Z'); while(c<='Z'&&c>='A')Query[++n]=c,c=getchar(); Decode(n); for(int i=n;i>=1;i--) Tree::insert(Query[i]); } else { do c=getchar();while(c!=' '); int n; scanf("%d",&n); while(n--) Tree::pop(); } } return 0; }
