可持久化线段树模板
#include<cstdio> #include<vector> #include<algorithm> #define N 100007 using namespace std; struct arr{ int ls,rs,cnt; }tr[N*20]; vector<int> s; int n,m,a[N],tot,root[N]; int find(int x){ return lower_bound(s.begin(),s.end(),x)-s.begin(); } int build(int l,int r){ int p=++tot,mid=(l+r)/2; if (l==r) return p; tr[p].ls=build(l,mid); tr[p].rs=build(mid+1,r); return p; } int inse(int p,int l,int r,int x){ int q=++tot,mid=(l+r)/2; tr[q].ls=tr[p].ls,tr[q].rs=tr[p].rs; if (l==r){ tr[q].cnt++; return q; } if (x<=mid) tr[q].ls=inse(tr[p].ls,l,mid,x); else tr[q].rs=inse(tr[p].rs,mid+1,r,x); tr[q].cnt=tr[tr[q].ls].cnt+tr[tr[q].rs].cnt; return q; } int que(int p,int q,int l,int r,int k){ int mid=(l+r)/2,c; if (l==r) return l; c=tr[tr[q].ls].cnt-tr[tr[p].ls].cnt; if (c>=k) return que(tr[p].ls,tr[q].ls,l,mid,k); return que(tr[p].rs,tr[q].rs,mid+1,r,k-c); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); s.push_back(a[i]); } sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); root[0]=build(0,s.size()-1); for (int i=1;i<=n;i++) root[i]=inse(root[i-1],0,s.size()-1,find(a[i])); for (int i=1;i<=m;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d ",s[que(root[l-1],root[r],0,s.size()-1,k)]); } }
treap模板
#include<cstdio> #include<algorithm> #define N 1000007 #define INF 1e8 using namespace std; struct arr{ int ls,rs,key,val,cnt,size; }tr[N]; int tot,root,n; int getnode(int key){ tr[++tot].key=key; srand(tot); tr[tot].val=rand(); tr[tot].cnt=tr[tot].size=1; return tot; } void renew(int p){ tr[p].size=tr[tr[p].ls].size+tr[tr[p].rs].size+tr[p].cnt; } void zuo(int &p){ int q=tr[p].rs; tr[p].rs=tr[q].ls; tr[q].ls=p; p=q; renew(tr[p].ls),renew(p); } void you(int &p){ int q=tr[p].ls; tr[p].ls=tr[q].rs; tr[q].rs=p; p=q; renew(tr[p].rs),renew(p); } void build(){ getnode(-INF),getnode(INF); root=1,tr[1].rs=2; if (tr[1].val<tr[2].val) zuo(root); } void add(int &p,int key){ if (!p){ p=getnode(key); return; } if (tr[p].key==key) tr[p].cnt++; if (tr[p].key<key){ add(tr[p].rs,key); if (tr[tr[p].rs].val>tr[p].val) zuo(p); } if (tr[p].key>key){ add(tr[p].ls,key); if (tr[tr[p].ls].val>tr[p].val) you(p); } renew(p); } void del(int &p,int key){ if (!p) return; if (tr[p].key==key) if (tr[p].cnt>1) tr[p].cnt--; else if (tr[p].ls||tr[p].rs) if (!tr[p].rs||tr[tr[p].ls].val>tr[tr[p].rs].val){ you(p); del(tr[p].rs,key); } else{ zuo(p); del(tr[p].ls,key); } else p=0; else if (tr[p].key>key) del(tr[p].ls,key); else del(tr[p].rs,key); renew(p); } int find1(int p,int key){ if (!p) return 0; if (tr[p].key==key) return tr[tr[p].ls].size+1; if (tr[p].key>key) return find1(tr[p].ls,key); return tr[tr[p].ls].size+tr[p].cnt+find1(tr[p].rs,key); } int find2(int p,int rank){ if (!p) return INF; if (tr[tr[p].ls].size>=rank) return find2(tr[p].ls,rank); if (tr[tr[p].ls].size+tr[p].cnt>=rank) return tr[p].key; return find2(tr[p].rs,rank-tr[tr[p].ls].size-tr[p].cnt); } int pre(int p,int x){ if (!p) return -INF; if (tr[p].key>=x) return pre(tr[p].ls,x); return max(tr[p].key,pre(tr[p].rs,x)); } int last(int p,int x){ if (!p) return INF; if (tr[p].key<=x) return last(tr[p].rs,x); return min(tr[p].key,last(tr[p].ls,x)); } int main(){ scanf("%d",&n); build(); for (int i=1;i<=n;i++){ int opt,x; scanf("%d%d",&opt,&x); if (opt==1) add(root,x); if (opt==2) del(root,x); if (opt==3) printf("%d ",find1(root,x)-1); if (opt==4) printf("%d ",find2(root,x+1)); if (opt==5) printf("%d ",pre(root,x)); if (opt==6) printf("%d ",last(root,x)); } }
ac自动机模板
#include<cstdio> #include<queue> #include<cstring> #define N 10001 #define M 1000001 #define S 51 using namespace std; int ans,tot,n,t,cnt[N*S],tr[N*S][26],ne[N*S]; char s[M]; void add(){ int p=0; for (int i=0;s[i]!=' ';i++){ int c=s[i]-'a'; if (tr[p][c]==0) tr[p][c]=++tot; p=tr[p][c]; } cnt[p]++; } void build(){ queue<int>q; for (int i=0;i<26;i++) if (tr[0][i]!=0) q.push(tr[0][i]); while (!q.empty()){ int x=q.front(); q.pop(); for (int i=0;i<26;i++) if (tr[x][i]!=0){ int t=tr[x][i],j=ne[x]; while (j!=0&&tr[j][i]==0) j=ne[j]; if (tr[j][i]!=0) j=tr[j][i]; ne[t]=j; q.push(t); } } } int main(){ scanf("%d",&t); while (t--){ memset(tr,0,sizeof(tr)); memset(cnt,0,sizeof(cnt)); memset(ne,0,sizeof(ne)); tot=0; scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%s",&s); add(); } build(); scanf("%s",&s); ans=0; for (int i=0,j=0;s[i]!=' ';i++){ int c=s[i]-'a'; while (j!=0&&tr[j][c]==0) j=ne[j]; if (tr[j][c]!=0) j=tr[j][c]; for (int p=j;p!=0;p=ne[p]) ans+=cnt[p],cnt[p]=0; } printf("%d ",ans); } }
splay模板
#include<cstdio> #include<algorithm> #define N 100007 using namespace std; struct arr{ int s[2],size,key,p,flag; }tr[N]; int root,n,m,tot; void renew(int p){ tr[p].size=tr[tr[p].s[0]].size+tr[tr[p].s[1]].size+1; } void putdown(int x){ if (tr[x].flag!=0){ swap(tr[x].s[0],tr[x].s[1]); tr[tr[x].s[0]].flag^=1; tr[tr[x].s[1]].flag^=1; tr[x].flag=0; } } void rotate(int x){ int y=tr[x].p,z=tr[y].p; int k=tr[y].s[1]==x; tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z; tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p = y; tr[x].s[k^1]=y,tr[y].p = x; renew(y),renew(x); } void splay(int x,int k){ while(tr[x].p!=k){ int y=tr[x].p,z=tr[y].p; if (z!=k) if ((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x); else rotate(y); rotate(x); } if (!k) root=x; } void add(int key){ int p=0,c,x=root; for (;x!=0;p=x,x=tr[x].s[c]) if (tr[x].key<key) c=1; else c=0; x=++tot; if (p!=0) tr[p].s[c]=x; tr[x].p=p,tr[x].key=key; splay(x,0); } void output(int x){ putdown(x); if (tr[x].s[0]!=0) output(tr[x].s[0]); if (tr[x].key>=1&&tr[x].key<=n) printf("%d ",tr[x].key); if (tr[x].s[1]!=0) output(tr[x].s[1]); } int get(int x){ int p=root; while (1==1){ putdown(p); if (tr[tr[p].s[0]].size+1>x) p=tr[p].s[0]; else if (tr[tr[p].s[0]].size+1==x) return p; else x-=tr[tr[p].s[0]].size+1,p=tr[p].s[1]; } } int main(){ scanf("%d%d",&n,&m); for (int i=0;i<=n+1;i++) add(i); for (int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); l=get(l),r=get(r+2); splay(l,0); splay(r,l); tr[tr[r].s[0]].flag^=1; } output(root); }