题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3223
从现在开始我要养成“一种树一个结构体”的好习惯
没什么好说的…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<bits/stdc++.h> #define MAXN 100010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } struct SplayTree{ int son[MAXN][2],fa[MAXN],key[MAXN],val[MAXN],sz[MAXN]; bool rev[MAXN]; int root,tot; bool getlr(int x){ return son[fa[x]][1]==x; } void uprev(int x){ if(!x)return; swap(son[x][0],son[x][1]); rev[x]^=1; } void pushup(int x){ sz[x]=sz[son[x][0]]+sz[son[x][1]]+1; } void pushdown(int x){ if(!x)return; if(rev[x]){ uprev(son[x][0]); uprev(son[x][1]); rev[x]^=1; } } void Rotate(int x){ int f=fa[x],ff=fa[f],which=getlr(x); son[f][which]=son[x][which^1]; fa[son[f][which]]=f;fa[f]=x; son[x][which^1]=f;fa[x]=ff; if(ff)son[ff][son[ff][1]==f]=x; pushup(f); pushup(x); } void splay(int x,int to){ pushdown(x); for(int f=fa[x]; f!=to; f=fa[x]){ if(fa[f]!=to)Rotate(getlr(x)==getlr(f)?f:x); Rotate(x); } if(to==0)root=x; } void ins(int v){ ++tot; if(root==0){ key[tot]=tot;val[tot]=v; sz[tot]=1;root=tot; return; } int now=root,f=0; while(1){ f=now; now=son[now][tot>key[now]]; if(now==0){ key[tot]=tot;val[tot]=v; sz[tot]=1;fa[tot]=f; son[f][tot>key[f]]=tot; pushup(f);splay(tot,0); return; } } } int getkth(int x){ int now=root; while(now){ pushdown(now); if(sz[son[now][0]]==x-1)return now; else if(sz[son[now][0]]<x)x-=sz[son[now][0]]+1,now=son[now][1]; else now=son[now][0]; } } void Reverse(int l,int r){ splay(getkth(l),0); splay(getkth(r+2),root); uprev(son[son[root][1]][0]); } void print(int x){ if(!x)return; pushdown(x); print(son[x][0]); if(val[x])printf("%d ",val[x]); print(son[x][1]); } }tree; int main(){ int n=rd(),m=rd(); tree.ins(0); for(int i=1; i<=n; i++)tree.ins(i); tree.ins(0); while(m--){ int x=rd(),y=rd(); tree.Reverse(x,y); } tree.print(tree.root); puts(""); return 0; } |
