#import<iostream>

#define W if

#define R return

using I=int;using V=void;const I F=2e6;I a[F],b[F],c[F],d[F],e[F],f[F],i=1,n,m,x,y,l,r,p,_,g;V K(I _){e[_]=e[c[_]]+e[d[_]]+1;}V J(I _){std::swap(c[_],d[_]);f[c[_]]^=1;f[d[_]]^=1;f[_]=0;}V B(I _,I S,I&l,I&r){W(!_){l=r=0;R;}W(f[_])J(_);W(e[c[_]]<S)l=_,B(d[_],S-e[c[_]]-1,d[_],r);else r=_,B(c[_],S,l,c[_]);K(_);}I A(I x,I y){W(!x|!y)R x+y;W(b[x]<b[y]){W(f[x])J(x);d[x]=A(d[x],y);K(x);R x;}W(f[y])J(y);c[y]=A(x,c[y]);K(y);R y;}V Z(I _){W(f[_])J(_);W(c[_])Z(c[_]);std::cout<<a[_]<<" ";W(d[_])Z(d[_]);}main(){std::cin>>n>>m;for(;i<=n;++i){a[++g]=i;b[g]=rand();e[g]=1;_=A(_,i);}while(m--){std::cin>>x>>y;B(_,y,l,r);B(l,x-1,l,p);f[p]^=1;_=A(A(l,p),r);}Z(_);}

這就是FHQTreap給我?guī)淼淖孕牛?/strong>