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
| #include <bits/stdc++.h> #define MAXN 200005 using namespace std; 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<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int fa[MAXN],ch[MAXN][2],size[MAXN],tag[MAXN]; #define lc(i) ch[i][0] #define rc(i) ch[i][1] inline void pushup(int i){ size[i]=size[lc(i)]+size[rc(i)]+1; } inline void pushdown(int i){ if (tag[i]){ tag[i]^=1; tag[lc(i)]^=1,tag[rc(i)]^=1; swap(lc(i),rc(i)); } } inline void rotate(int x,int &k){ int y=fa[x],z=fa[y]; bool p=(lc(y)==x); if (y==k) k=x; else { if (lc(z)==y) lc(z)=x; else rc(z)=x; } ch[y][!p]=ch[x][p]; fa[ch[y][!p]]=y,ch[x][p]=y; fa[y]=x,fa[x]=z; pushup(x),pushup(y); } inline void splay(int x,int &k){ while (x!=k){ int y=fa[x],z=fa[y]; if (y!=k){ if ((lc(y)==x)^(lc(z)==y)) rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int l,int r,int f){ if (l>r) return ; int mid=(l+r)>>1; if (mid<f) lc(f)=mid; else rc(f)=mid; fa[mid]=f;size[mid]=1; if (l==r) return ; build(l,mid-1,mid),build(mid+1,r,mid); pushup(mid); } int Find(int x,int k){ pushdown(x); if (k==size[lc(x)]+1) return x; else if (k<=size[lc(x)]) return Find(lc(x),k); else return Find(rc(x),k-size[lc(x)]-1); } int root; void Update(int l,int r){ int x=Find(root,l),y=Find(root,r+2); splay(x,root),splay(y,rc(x)); tag[lc(y)]^=1; } int main(){ int n=read(),m=read(); root=(n+3)/2,build(1,n+2,root); for (register int i=1;i<=m;++i){ int l=read(),r=read(); Update(l,r); } for (register int i=2;i<=n+1;++i){ printf("%d ",Find(root,i)-1); } }
|