第一棵伸展树，各种调试模板……TVT
对于 1 n 这种查询我处理的不太好，之前序列前后没有添加冗余节点，一直Runtime Error。
后来加上冗余节点之后又出了别的状况，因为多了 0 和 n+1 这两个节点，并且每次截取翻转添加到序列最后，因此无法确定 n+1 这个节点在序列的哪个位置。
比如（括号中的为添加的冗余节点）：
（0） 1 2 3 4 5 （6）
我把[3,4]截取翻转添加到序列尾部，会变成这样：
（0）1 2 5 （6）4 3
此时我如果再希望截取[3,4]，期望的结果应该是：
1 2 3 4 5
而实际上会变成：
（0）1 2 4 3 （6） 5
我用了一种挺麻烦的方式解决的这个问题：
就是让伸展树在冗余节点n+1之前的位置再分裂一次，每次把截取的序列添加到节点n+1的前面，一直维持n+1在序列最末尾，这样就不会有干扰了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; struct Node
{
Node *ch[];
int v, s;
int flip;
Node( int v ):v(v)
{
ch[] = ch[] = NULL;
s = ;
flip = ;
}
int cmp( int x ) const
{
int t = ( ch[] == NULL ) ? : ch[]->s;
if ( t >= x ) return ;
if ( t + == x ) return -;
return ;
}
void maintain()
{
s = ;
if ( ch[] != NULL ) s += ch[]->s;
if ( ch[] != NULL ) s += ch[]->s;
return;
}
void pushDown()
{
if ( flip )
{
flip = ;
swap( ch[], ch[] );
if ( ch[] != NULL ) ch[]->flip = !ch[]->flip;
if ( ch[] != NULL ) ch[]->flip = !ch[]->flip;
}
}
}; int n, m; void Rotate( Node* &o, int d ) //d=0 左旋 d=1 右旋
{
Node *k = o->ch[ d ^ ];
o->ch[ d ^ ] = k->ch[d];
k->ch[d] = o;
o = k;
o->ch[d]->maintain();
o->maintain();
return;
} void splay( Node* &o, int k )
{
o->pushDown();
int d = o->cmp(k);
if ( d == )
{
if ( o->ch[] != NULL )
k -= o->ch[]->s;
--k;
}
if ( d != - )
{
Node *p = o->ch[d];
p->pushDown();
int d2 = p->cmp(k);
int k2 = k;
if ( d2 == )
{
if ( p->ch[] != NULL )
k2 -= p->ch[]->s;
--k2;
}
if ( d2 != - )
{
splay( p->ch[d2], k2 );
if ( d == d2 ) Rotate( o, d ^ );
else Rotate( o->ch[d], d );
}
Rotate( o, d ^ );
}
return;
} Node *Merge( Node *left, Node *right )
{
splay( left, left->s );
left->ch[] = right;
left->maintain();
return left;
} void Split( Node *o, int k, Node* &left, Node* &right )
{
splay( o, k );
left = o;
right = o->ch[];
o->ch[] = NULL;
left->maintain();
return;
} void build( Node* &o, int l, int r )
{
int m = ( l + r ) >> ;
o = new Node(m);
if ( l < m ) build( o->ch[], l, m - );
if ( r > m ) build( o->ch[], m + , r );
o->maintain();
return;
} void DFS( Node *cur )
{
cur->pushDown();
if ( cur->ch[] ) DFS( cur->ch[] );
if ( cur->v && cur->v != n + ) printf( "%d\n", cur->v );
if ( cur->ch[] ) DFS( cur->ch[] );
return;
} void DeleteTree( Node *cur )
{
if ( cur->ch[] ) DeleteTree( cur->ch[] );
if ( cur->ch[] ) DeleteTree( cur->ch[] );
delete cur;
return;
} Node *root; int main()
{
while ( ~scanf( "%d%d", &n, &m ) )
{
root = NULL;
build( root, , n + ); //前后各加了一个冗余节点
while ( m-- )
{
int a, b;
scanf( "%d%d", &a, &b );
Node *left, *mid, *right, *o, *tmp; Split( root, a, left, o );
Split( o, b - a + , mid, right ); if ( right->s - > )
{
Split( right, right->s - , tmp, o );
mid->flip ^= ;
root = Merge( left, Merge( Merge( tmp, mid ), o ) );
}
else
{
mid->flip ^= ;
root = Merge( left, Merge( mid, right ) );
}
}
DFS( root );
DeleteTree( root );
}
return ;
}