把一堆splay 的题目都写完了，可以慢慢退坑了。。
splay 是个好东西用好了比treap还好 好写好调 好AC。。。复杂度不太懂反正均摊logn。。最后时间复杂度多乘上logn即可。
我觉得有点空虚 是必须要总结一下了，又再次有点迷了，加快速度 quick quick quick！！！
这道题是一个splay的模板题却有点复杂，因为我当时迷了很久。。细节有点多第一个操作和第二个操作都比较简单首先先把这个数字删掉然后再进行插入即可。
好像是有点复杂了当然这也是可以的 更简单的做法是如果是将x放到上面那就先将x旋转到根再把x的左子树放到自己后继的左子树上即可。放到底部同理。
第二个操作 也就是交换与x相邻的两个点的位置 这个其实也是比较简单的吧 当时困扰了我很久 自己想出来加上对拍一种方法是我先将x旋转到根 然后寻找x的前驱或者后继 然后此时如果x的前驱和后继相连的话需要特判为什么呢我们可以设想一下如果不相连的话就直接交换即可。相连那这个关系就不能直接的套化了会出现错误此时特判一下即可。
剩下的就是 排名和 查找了。
#include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 10000000000000ll #define ll long long #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define s(x) t[x].s #define h(x) t[x].h #define tag(x) t[x].tag #define g(x) t[x].g using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } inline void put(int x) { x<0?putchar(‘-‘),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘\n‘);return; } const int MAXN=80010; int n,m,rt; int a[MAXN],pos[MAXN]; int f[MAXN],c[MAXN][2],sz[MAXN],key[MAXN],s; char b[10]; inline int get(int x){return c[f[x]][1]==x;} inline void pushup(int x) { if(x) { sz[x]=1; if(c[x][0])sz[x]+=sz[c[x][0]]; if(c[x][1])sz[x]+=sz[c[x][1]]; return; } } inline void build(int l,int r,int fa) { if(l>r)return; int mid=(l+r)>>1; if(mid<fa)c[fa][0]=mid; else c[fa][1]=mid; sz[mid]=1;key[mid]=a[mid];f[mid]=fa;pos[a[mid]]=mid; build(l,mid-1,mid); build(mid+1,r,mid); pushup(mid); } inline int calculate(int k,int now) { if(sz[c[now][0]]>=k)return calculate(k,c[now][0]); if(sz[c[now][0]]+1==k)return now; return calculate(k-sz[c[now][0]]-1,c[now][1]); } inline void rotate(int x) { int old=f[x],oldf=f[old],k=get(x); c[old][k]=c[x][k^1];f[c[old][k]]=old; c[x][k^1]=old;f[old]=x;f[x]=oldf; if(oldf)c[oldf][c[oldf][1]==old]=x; pushup(old);pushup(x);return; } inline void splay(int x) { for(int fa;(fa=f[x]);rotate(x)) if(f[fa])rotate(get(x)==get(fa)?fa:x); rt=x;return; } inline void top(int x) { x=pos[x];splay(x); if(!c[x][0])return; if(!c[x][1]){c[x][1]=c[x][0];f[c[x][1]]=x;c[x][0]=0;return;} int y=calculate(sz[c[x][0]]+2,rt); c[y][0]=c[x][0];f[c[x][0]]=y;c[x][0]=0; splay(y);return; } inline void bottom(int x) { x=pos[x];splay(x); if(!c[x][1])return; if(!c[x][0]){c[x][0]=c[x][1];c[x][1]=0;return;} int y=calculate(sz[c[x][0]],rt); c[y][1]=c[x][1];f[c[x][1]]=y;c[x][1]=0; splay(y);return; } inline void insert(int x,int y) { if(y==0)return; x=pos[x];splay(x); int z,k; if(y==1)z=calculate(sz[c[x][0]]+2,rt); else z=calculate(sz[c[x][0]],rt); k=get(z); int u=c[z][0],u1=c[z][1]; if(c[x][k]==z) { c[z][0]=c[x][0];c[z][1]=c[x][1]; c[z][k]=x;c[x][0]=u;c[x][1]=u1; f[c[x][0]]=f[c[x][1]]=x; f[c[z][0]]=f[c[z][1]]=z; rt=z;f[rt]=0;pushup(x);pushup(z);return; } c[z][0]=c[x][0];c[z][1]=c[x][1]; f[c[x][0]]=f[c[x][1]]=z; f[x]=f[z];c[f[x]][k]=x; c[x][0]=u;c[x][1]=u1;f[u]=f[u1]=x; f[z]=0;rt=z;pushup(x);pushup(z);return; } int main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read();m=read();rt=(n+1)>>1; for(int i=1;i<=n;++i) { //if(a[i]>n){puts("wwww");return 0;} a[i]=read(); } build(1,n,rt);f[rt]=0;//put(sz[rt]); for(int i=1;i<=m;++i) { int x,y; scanf("%s",b+1); x=read(); if(b[1]==‘T‘)top(x); if(b[1]==‘B‘)bottom(x); if(b[1]==‘I‘)y=read(),insert(x,y); if(b[1]==‘A‘)splay(pos[x]),put(sz[c[pos[x]][0]]); if(b[1]==‘Q‘)put(key[calculate(x,rt)]); } return 0; }
第二次写这道题了 现在的我已经可以轻松的把握这道题的解法了的确线段树翻转区间的确非常困难，至少我不知道怎么翻转但是平衡树翻转区间还是很容易的。
直接查找l-1 r+1 即可记得下传标记即可。然后最后按照中序遍历输出即可这个操作我不太会 但是直接查找即可。
#include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 2147483646 #define ll long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getc();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getc();} return x*f; } inline void put(int x) { x<0?putchar(‘-‘),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘ ‘);return; } const int MAXN=100010; int n,m; int f[MAXN],c[MAXN][2],rev[MAXN],sz[MAXN],key[MAXN],cnt[MAXN],s,root; int re[MAXN]; inline void pushup(int x) { if(x) { sz[x]=cnt[x]; if(c[x][0])sz[x]+=sz[c[x][0]]; if(c[x][1])sz[x]+=sz[c[x][1]]; } return; } inline int get(int x){return x==c[f[x]][1];} inline void rotate(int x) { int old=f[x],oldf=f[old],k=get(x); c[old][k]=c[x][k^1];f[c[old][k]]=old; c[x][k^1]=old;f[old]=x; f[x]=oldf; if(oldf)c[oldf][c[oldf][1]==old]=x; pushup(old);pushup(x); } inline void splay(int x,int goal) { for(int fa;(fa=f[x])!=goal;rotate(x)) if(f[fa]!=goal)rotate((get(x)==get(fa))?fa:x); if(!goal)root=x; } inline void insert(int x) { if(root==0) { ++s;key[s]=x;root=x; cnt[s]=sz[s]=1; f[s]=c[s][0]=c[s][1]=0; return; } int now=root,fa=0; while(1) { if(x==key[now]) { ++cnt[now];pushup(now);pushup(fa);splay(now,0);return; } fa=now;now=c[now][key[now]<x]; if(!now) { ++s;sz[s]=cnt[s]=1; c[s][0]=c[s][1]=0; c[fa][x>key[fa]]=s; f[s]=fa;key[s]=x; pushup(fa);splay(s,0);return; } } } inline void pushdown(int x) { swap(c[x][1],c[x][0]); re[c[x][1]]^=1; re[c[x][0]]^=1; re[x]=0; } inline int rank(int x,int k) { if(re[x])pushdown(x); int w=sz[c[x][0]]; if(k==w+1)return x; if(k<=w)return rank(c[x][0],k); return rank(c[x][1],k-w-1); } inline void reversal(int l,int r) { int x=rank(root,l-1),y=rank(root,r+1); splay(y,0); //cout<<root<<‘ ‘<<c[root][0]<<endl; splay(x,root); //cout<<c[root][0]<<endl; re[c[x][1]]^=1; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n+2;++i)insert(i); for(int i=1;i<=m;++i) { int l,r; l=read()+1;r=read()+1; reversal(l,r); } for(int i=2;i<=n;++i) { //cout<<rank(root,i)<<endl; put(key[rank(root,i)]-1); } printf("%d\n",key[rank(root,n+1)]-1); return 0; }
这道题的特点我总结一下 splay的插入如果给你所有排列了进行直接建树建成一个非常平衡的树 复杂度O(n) 然后就是一些操作了。
还有懒标记这个东西 有两种写法 就是说这样当你要将要进去你的左右两边子树的时候下传标记，当然一种做法是你还没有进去左右两边的子树交换过了当你将要进去的时候你下传标记然后进行各自子树内部的再次交换。显然这个是和线段树差不多的要固定一个写法，不固定的话写着写着就迷了。这里我固定一个写法：就类似于线段树吧 我到达这个点我就把这个点所联系的直接改变掉。然后下传标记也是这样的。确定好了以后就这样写。
这道题的难度我觉得很不错 想出来其实特别有成就感但是我是依靠其他途径想出来的 例如 这道题的前置题区间众数（超过一半版本）
这也是我第一次写多颗splay 其实和单棵splay 是一样的 也就是一棵主席树和多颗主席树的区别。
首先求出区间众数 我们的区间众数是不具可加性的因为一个小区间的众数基本上是不可转移到一个大区间的众数的。但是有一种叫做摩尔根投票法 我们采用数字对消的方式来求出区间的众数因为如果是答案的话进行区间对消最坏的情况也是可以得到答案的。然后答案却需要判定 判定这个答案在当前区间中出现是否超过一半。
原本我们需要对区间整体的数字都求一遍现在可以直接求了。然后修改的话也是一个单调修改的过程。问题成功转化为一个区间内求一个数字出现的次数 。显然不带修改多次询问我可以 搞前缀和怎么样我刚学会的技能一道题中前缀和搞这个特别爽 dp的过程。空间不够呢？那么此时考虑主席树可我们针对每一个位置开主席树的话修改要树套树 显然空间直接爆掉。转换思路 我们对每个人开主席树下标是区间然后复杂度nlogn 空间nlogn+klogn哇很完美但是经过严密的计算还是会爆掉别灰心至少这样我们已经可以拿到80分了。然后再次思考有没有什么更省空间的平衡树好了splay啊空间复杂度O(n) 然后直接对每个点开一棵平衡树即可。
//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 10000000000000ll #define ll long long #define l(x) t[x].l #define r(x) t[x].r #define v(x) t[x].v #define sum(x) t[x].sum #define R register using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { R int x=0,f=1;char ch=getc(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getc();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getc();} return x*f; } inline void put(R int x) { x<0?putchar(‘-‘),x=-x:0; R int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘\n‘);return; } //总统选举 线段树+splay const int MAXN=500010; int n,m,cnt; int a[MAXN]; int rt[MAXN],c[MAXN][2],sz[MAXN],f[MAXN]; struct wy { int l,r; int sum; int v; wy(){l=r=sum=v=0;} }t[MAXN<<2]; inline void pushup(R int x) { if(x) { sz[x]=1; if(c[x][1])sz[x]+=sz[c[x][1]]; if(c[x][0])sz[x]+=sz[c[x][0]]; return; } } inline void build(R int p,R int l,R int r) { l(p)=l;r(p)=r; if(l==r){sum(p)=a[l];++v(p);return;} R int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); if(sum(p<<1)==sum(p<<1|1)) { sum(p)=sum(p<<1); v(p)=v(p<<1)+v(p<<1|1); return; } sum(p)=v(p<<1)>=v(p<<1|1)?sum(p<<1):sum(p<<1|1); v(p)=v(p<<1)>=v(p<<1|1)?v(p<<1)-v(p<<1|1):v(p<<1|1)-v(p<<1); return; } inline wy ask(R int p,R int l,R int r) { if(l<=l(p)&&r>=r(p))return t[p]; R int mid=(l(p)+r(p))>>1; wy a,b; if(l<=mid)a=ask(p<<1,l,r); if(r>mid)b=ask(p<<1|1,l,r); if(a.sum==b.sum) { a.v+=b.v; return a; } a.sum=a.v>=b.v?a.sum:b.sum; a.v=a.v>=b.v?a.v-b.v:b.v-a.v; return a; } inline int get(R int x){return c[f[x]][1]==x;} inline void rotate(R int x) { R int old=f[x],oldf=f[old],k=get(x); c[old][k]=c[x][k^1];f[c[old][k]]=old; c[x][k^1]=old;f[old]=x;f[x]=oldf; if(oldf)c[oldf][c[oldf][1]==old]=x; pushup(old);pushup(x);return; } inline void splay(R int x,R int y) { for(R int fa;(fa=f[x]);rotate(x)) if(f[fa])rotate(get(fa)==get(x)?fa:x); rt[y]=x; } inline int rank(R int root,R int x) { R int sum=0,now=rt[root],fa=now; if(!now)return 0; while(1) { if(!now){splay(fa,root);return sum;} if(now==x){sum+=sz[c[now][0]]+1;splay(now,root);return sum;} if(now<x) { sum+=sz[c[now][0]]+1; fa=now; now=c[now][1]; } else fa=now,now=c[now][0]; } } inline void insert(R int x,R int y) { if(rt[y]==0){sz[x]=1;rt[y]=x;return;} R int now=rt[y],fa=0; while(1) { fa=now;now=c[now][now<x]; if(!now) { f[x]=fa;sz[x]=1; c[fa][fa<x]=x; pushup(fa);splay(x,y);return; } } } inline void cle(R int x){f[x]=c[x][0]=c[x][1]=sz[x]=0;} inline int getpre(R int root) { R int now=rt[root]; now=c[now][0]; while(c[now][1])now=c[now][1]; splay(now,root); return now; } inline void del(R int x,R int root) { splay(x,root); if(!c[x][0]&&!c[x][1]){cle(x);rt[root]=0;return;} R int old=x; if(!c[x][0]){rt[root]=c[x][1];f[c[x][1]]=0;cle(old);return;} if(!c[x][1]){rt[root]=c[x][0];f[c[x][0]]=0;cle(old);return;} R int ls=getpre(root); splay(ls,root);c[ls][1]=c[old][1]; f[c[old][1]]=ls;cle(old);pushup(ls); return; } inline void change(R int p,R int x,R int w,R int k) { if(l(p)==r(p)){v(p)+=k;if(v(p)==0)sum(p)=0;else sum(p)=w;return;} R int mid=(l(p)+r(p))>>1; if(x<=mid)change(p<<1,x,w,k); else change(p<<1|1,x,w,k); if(sum(p<<1)==sum(p<<1|1)) { sum(p)=sum(p<<1); v(p)=v(p<<1)+v(p<<1|1); return; } sum(p)=v(p<<1)>=v(p<<1|1)?sum(p<<1):sum(p<<1|1); v(p)=v(p<<1)>=v(p<<1|1)?v(p<<1)-v(p<<1|1):v(p<<1|1)-v(p<<1); } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(R int i=1;i<=n;++i) { a[i]=read(); insert(i,a[i]); } build(1,1,n); for(R int i=1;i<=m;++i) { R int x,y,s,k,w,sum,pos; x=read();y=read();s=read();k=read(); w=ask(1,x,y).sum; sum=rank(w,y)-rank(w,x-1); pos=sum>((y-x+1)>>1)?w:s; for(R int j=1;j<=k;++j) { R int p; p=read();//if(i==5)cout<<p<<endl; if(a[p]==pos)continue; del(p,a[p]); insert(p,pos); change(1,p,a[p],-1); change(1,p,pos,1); a[p]=pos; } put(pos); } R int w=ask(1,1,n).sum; R int sum=rank(w,n); R int pos=sum>(n>>1)?w:-1; put(pos); return 0; }
注意这里要多splay几下不然会T掉。。
这道题的话 我自认为时最毒瘤的题目了 非常ex 我想都不想想尽管是一个模板 但是我仍不是很想思考。。。
算了我写的时候翻了下题解导致思考不足所以现在感觉有点虚早知道自己想了。。。
我在这里再次手推一下并且保证下次再写一遍好了 这道好题我一定会再写一遍那时这道题将拦不住我的。
插入 由于是连续的插入直接一个一个插入的话直接就是一个nlogn的了总共插入4000000这么多的数字不用我说都会时间就有点紧张了，不妨先O(n)建树再插入这样更好写一些。 注意在插入的同时序号和值的转换。
原文：https://www.cnblogs.com/chdy/p/10881776.html
