是NOI2003Editor的一个子任务
#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std; struct Splay {
int pre[maxn], son[maxn][], siz[maxn], rev[maxn], root; void update( int nd ) {
siz[nd] = siz[son[nd][]]+siz[son[nd][]]+;
}
void pushdown( int nd ) {
if( rev[nd] ) {
swap( son[nd][], son[nd][] );
if( son[nd][] ) rev[son[nd][]] ^= ;
if( son[nd][] ) rev[son[nd][]] ^= ;
rev[nd] = ;
}
}
int build( int lf, int rg, int p ) {
if( lf>rg ) return ;
int mid = (lf+rg)>>;
pre[mid] = p;
rev[mid] = ;
son[mid][] = build( lf, mid-, mid );
son[mid][] = build( mid+, rg, mid );
update( mid );
return mid;
}
void init( int n ) {
root = build( , n+, );
}
void rotate( int nd, int d ) {
int p = pre[nd];
int s = son[nd][!d];
int ss = son[s][d]; son[nd][!d] = ss;
son[s][d] = nd;
if( p ) son[p][ nd==son[p][] ] = s;
else root = s; pre[nd] = s;
pre[s] = p;
if( ss ) pre[ss] = nd; update( nd );
update( s );
}
void splay( int nd, int top ) {
while( pre[nd]!=top ) {
int p = pre[nd];
int nl = nd==son[p][];
if( pre[p]==top ) {
rotate( p, nl );
} else {
int pp = pre[p];
int pl = p==son[pp][];
if( nl==pl ) {
rotate( pp, pl );
rotate( p, nl );
} else {
rotate( p, nl );
rotate( pp, pl );
}
} }
}
int find( int pos ) {
int nd = root;
while() {
pushdown( nd );
int ls = siz[son[nd][]];
if( pos<=ls ) {
nd = son[nd][];
} else if( pos>=ls+ ) {
nd = son[nd][];
pos -= ls+;
} else {
splay( nd, );
return nd;
}
}
}
void reverse( int lf, int rg ) {
int lnd = find(lf-);
int rnd = find(rg+);
splay( lnd, );
splay( rnd, lnd );
rev[son[rnd][]] ^= ;
pushdown( son[rnd][] );
splay( son[rnd][], );
}
int get( int pos ) {
return find(pos);
}
}; int n, m;
Splay T;
int main() {
scanf( "%d%d", &n, &m );
T.init( n );
for( int i=,lf,rg; i<=m; i++ ) {
scanf( "%d%d", &lf, &rg );
T.reverse( lf+, rg+ );
}
for( int i=; i<=n+; i++ )
printf( "%d ", T.get(i)- );
}