|
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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <bits/stdc++.h> #define MAXN 100010 #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct splay_tree{ int son[MAXN][2],fa[MAXN],val[MAXN],key[MAXN],sz[MAXN]; int tot,root; bool rev[MAXN]; void init(){ memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(rev,0,sizeof(rev)); val[1]=-inf,val[2]=inf; key[1]=-inf,key[2]=inf; son[2][0]=1; sz[2]=2;sz[1]=1; fa[1]=2; tot=2; root=2; } void Set(int x,int f,int w){ son[f][w]=x; fa[x]=f; } void pushup(int x){ sz[x]=sz[son[x][0]]+sz[son[x][1]]+1; } void add(int x,int k){ int now=root,pre; while(1){ pre=now; now=son[now][k>key[now]]; if(!now){ now=++tot; Set(now,pre,k>key[pre]); val[now]=x; key[now]=k; sz[now]=1; pushup(pre); splay(x,0); return; } } } bool getlr(int x){ return son[fa[x]][1]==x; } void Rev(int x){ if(!x)return; rev[x]^=1; swap(son[x][0],son[x][1]); } void pushdown(int x){ if(!x)return; if(rev[x]){ Rev(son[x][0]); Rev(son[x][1]); rev[x]^=1; } } void Rotate(int x){ int f=fa[x],ff=fa[f],w=getlr(x); Set(x,ff,getlr(f)); Set(son[x][w^1],f,w); Set(f,x,w^1); 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; } 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 spilit(int l,int r){ splay(getkth(l),0); splay(getkth(r+2),root); } void Reverse(int l,int r){ spilit(l,r); Rev(son[son[root][1]][0]); } void print(int x){ if(!x)return; pushdown(x); print(son[x][0]); if(val[x]!=inf && val[x]!=-inf)printf("%d ",val[x]); print(son[x][1]); } }splay; int n,m; int main(){ n=rd(),m=rd(); splay.init(); for(int i=1; i<=n; i++)splay.add(i,i); while(m--){ int x=rd(),y=rd(); splay.Reverse(x,y); } splay.print(splay.root); puts(""); return 0; } |
