壓了好久了，splay區間翻轉的模板，我的好多模板都是照zyf2000寫的。同樣貼代碼跑.
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm> using namespace std;const int maxn=110000,inf=10000000;int ch[maxn][2],f[maxn],size[maxn],key[maxn],delta[maxn],a[maxn]; int n,m,x,y,root,sz;void updata(int x){ size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}bool get(int x){return ch[f[x]][1]==x;}void pushdown(int x){ if (x&&delta[x]) { delta[ch[x][1]]^=1; delta[ch[x][0]]^=1; swap(ch[x][0],ch[x][1]); delta[x]=0; }}int build(int l,int r,int fa){ if (l>r)return 0; int mid=(l+r)>>1; int now=++sz; key[now]=a[mid];f[now]=fa;delta[now]=0; int leftchild=build(l,mid-1,now); int rightchild=build(mid+1,r,now); ch[now][0]=leftchild;ch[now][1]=rightchild;updata(now); return now; }void rotate (int x){ pushdown(f[x]);pushdown(x); int old=f[x],oldf=f[old],which=get(x); ch[old][which]=ch[x][which^1];f[ch[old][which]]=old; ch[x][which^1]=old;f[old]=x; f[x]=oldf; if (oldf) ch[oldf][ch[oldf][1]==old]=x; updata(old);updata(x); }void splay(int x,int tar){ for (int fa;(fa=f[x])!=tar;rotate(x)) if (f[fa]!=tar) rotate((get(x)==get(fa))?fa:x); if(tar==0) root=x; }int find(int x){ int now=root; while(1) { pushdown(now); if (x<=size[ch[now][0]]) now=ch[now][0]; else { x-=size[ch[now][0]]+1; if (x==0)return now; now=ch[now][1]; } } } void PRint(int now){ pushdown(now); if (ch[now][0])print(ch[now][0]); if (key[now]!=inf&&key[now]!=-inf)printf("%d ",key[now]); if (ch[now][1])print(ch[now][1]);}int main(){ scanf("%d%d",&n,&m); a[1]=-inf;a[n+2]=inf; for (int i=1;i<=n;i++) a[i+1]=i; sz=0; root=build(1,n+2,0); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if (x>=y)continue; int aa=find(x); int bb=find(y+2); splay(aa,0); splay(bb,aa); delta[ch[ch[root][1]][0]]^=1; } print(root);}新聞熱點
疑難解答
