Splay 每个节点维护一个区间。
/**************************************************************
Problem: 3595
User: idy002
Language: C++
Result: Accepted
Time:5428 ms
Memory:56020 kb
****************************************************************/ #include <cstdio>
#include <map>
#define N 2000000
using namespace std; map<int,int> atob, btoa;
map<int,int> rng_id; struct Splay {
int son[N][], pre[N], xlf[N], xrg[N], siz[N], root, ntot; int newnode( int p, int lf, int rg ) {
if( lf>rg ) return ;
int nd = ++ntot;
son[nd][] = son[nd][] = ;
pre[nd] = p;
xlf[nd] = lf;
xrg[nd] = rg;
siz[nd] = rg-lf+;
return nd;
}
void update( int nd ) {
siz[nd] = siz[son[nd][]]+siz[son[nd][]]+(xrg[nd]-xlf[nd]+);
}
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 );
}
}
}
}
void init( int lf, int rg ) {
ntot = ;
root = newnode( , lf, rg );
rng_id[rg] = root;
}
void make_one( int nd ) {
int lnd, rnd;
splay( nd );
lnd = son[nd][];
rnd = son[nd][];
while( son[lnd][] ) lnd=son[lnd][];
while( son[rnd][] ) rnd=son[rnd][];
if( lnd && rnd ) {
splay( lnd );
splay( rnd, lnd );
} else if( lnd ) {
splay( lnd );
} else if( rnd ) {
splay( rnd );
}
}
void split( int nd, int pos ) {
if( xlf[nd]==xrg[nd] ) return;
make_one( nd );
int lnd, rnd;
lnd = newnode( , xlf[nd], pos- );
rnd = newnode( , pos+, xrg[nd] );
son[nd][] = lnd;
son[nd][] = rnd;
if( lnd ) {
pre[lnd] = nd;
rng_id[pos-] = lnd;
}
if( rnd ) {
pre[rnd] = nd;
rng_id[xrg[nd]] = rnd;
}
rng_id[pos] = nd;
xlf[nd] = xrg[nd] = pos;
update( nd );
splay( nd );
}
void erase( int nd ) {
make_one( nd );
int p=pre[nd];
pre[nd] = ;
if( p ) {
son[p][ nd==son[p][] ] = ;
pre[nd] = ;
update( p );
splay( p );
} else {
root = ;
pre[nd] = ;
}
}
void push_front( int nn ) {
if( !root ) {
root = nn;
return;
}
int nd=root;
while( son[nd][] ) nd=son[nd][];
son[nd][] = nn;
pre[nn] = nd;
splay( nn );
}
void push_back( int nn ) {
if( !root ) {
root = nn;
return;
}
int nd=root;
while( son[nd][] ) nd=son[nd][];
son[nd][] = nn;
pre[nn] = nd;
splay(nn);
}
int rank( int nd ) {
int rt=siz[son[nd][]]+;
int nnd=nd;
while( pre[nd] ) {
int p=pre[nd];
if( nd==son[p][] ) rt += siz[son[p][]]+(xrg[p]-xlf[p]+);
nd=p;
}
splay(nnd);
return rt;
}
int nth( int k ) {
int nd=root;
while() {
int ls=siz[son[nd][]];
int lcs=ls+(xrg[nd]-xlf[nd]+);
if( k<=ls ) {
nd = son[nd][];
} else if( k<=lcs ) {
int rt = xlf[nd]+k-ls-;
splay( nd );
return rt;
} else {
k -= lcs;
nd = son[nd][];
}
}
}
}T; int n, m;
int main() {
scanf( "%d%d", &n, &m );
T.init( , n );
int la = ;
for( int i=; i<=m; i++ ) {
int opt, x, y;
scanf( "%d%d", &opt, &x );
x -= la;
if( opt== ) {
scanf( "%d", &y );
y -= la;
int pos = btoa.count(x) ? btoa[x] : x;
atob[pos] = y;
btoa[y] = pos;
int nd= rng_id.lower_bound( pos )->second;
T.split( nd, pos );
printf( "%d\n", la=T.rank(nd) );
} else if( opt== ) {
int pos = btoa.count(x) ? btoa[x] : x;
int nd=rng_id.lower_bound( pos )->second;
T.split( nd, pos );
printf( "%d\n", la=T.rank(nd) );
T.erase( nd );
T.push_front( nd );
} else if( opt== ) {
int pos = btoa.count(x) ? btoa[x] : x;
int nd = rng_id.lower_bound( pos )->second;
T.split( nd, pos );
printf( "%d\n", la=T.rank(nd) );
T.erase( nd );
T.push_back( nd );
} else {
int pos=T.nth(x);
int b = atob.count(pos) ? atob[pos] : pos;
printf( "%d\n", la=b );
}
}
}