题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1269
大致思路：
用splay维护整个文本信息，splay树的中序遍历即为该文本。
收获：
1、可以先在文本开始和结尾个插入一个节点，然后每次操作都适当调整位置，这样可以减少特判（插入一段文本到0位置，在最后插入一段文本。。。）
2、查找一段文本[lf,rg]，可以先找到位置为lf-1的节点（因为1，不用特判没有了），splay到根，再找到rg+1的节点，旋转到根的下面，这样根右子节点的左子树就是我们要找的内容。
3、翻转一段文本，有点像线段树，给节点打上lazy标记，因为删除、插入、翻转等操作都是建立在查找制定位置的节点这一操作上的，所以我们只需要在查找操作中下传标记。（下传标记和标记都要用“反转”方式而不是“设置”方式，因为以前有可能已经有了标志）
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define maxn 2100000 5 using namespace std; 6 7 struct Splay { 8 int pre[maxn], son[maxn][2], siz[maxn], ntot, root; 9 char val[maxn]; 10 bool inv[maxn]; 11 int trash[maxn], stot; 12 13 int newnode( char ch, int p ) { 14 int nd; 15 if( stot ) nd = trash[stot--]; 16 else nd = ++ntot; 17 val[nd] = ch; 18 pre[nd] = p; 19 son[nd][0] = son[nd][1] = 0; 20 siz[nd] = 1; 21 inv[nd] = false; 22 return nd; 23 } 24 Splay():ntot(0),stot(0){ 25 root = newnode( ‘^‘, 0 ); 26 son[root][1] = newnode( ‘$‘, root ); 27 } 28 void pushdown( int nd ) { 29 if( inv[nd] ) { 30 swap( son[nd][0], son[nd][1] ); 31 if( son[nd][0] ) inv[son[nd][0]] ^= true; 32 if( son[nd][1] ) inv[son[nd][1]] ^= true; 33 inv[nd] = false; 34 } 35 } 36 void update( int nd ) { 37 siz[nd] = siz[son[nd][0]]+siz[son[nd][1]]+1; 38 } 39 void rotate( int nd, int d ) { 40 int p = pre[nd]; 41 int s = son[nd][!d]; 42 int ss = son[s][d]; 43 44 son[nd][!d] = ss; 45 son[s][d] = nd; 46 if( p ) son[p][ nd==son[p][1] ] = s; 47 else root = s; 48 49 pre[nd] = s; 50 pre[s] = p; 51 if( ss ) pre[ss] = nd; 52 53 update( nd ); 54 update( s ); 55 } 56 void splay( int nd, int top ) { 57 while( pre[nd]!=top ) { 58 int p = pre[nd]; 59 int nl = nd==son[p][0]; 60 if( pre[p]==top ) { 61 rotate( p, nl ); 62 } else { 63 int pp = pre[p]; 64 int pl = p==son[pp][0]; 65 if( pl==nl ) { 66 rotate( pp, pl ); 67 rotate( p, nl ); 68 } else { 69 rotate( p, nl ); 70 rotate( pp, pl ); 71 } 72 } 73 } 74 } 75 int find( int pos ) { 76 int nd = root; 77 while(1) { 78 pushdown( nd ); 79 int ls = siz[son[nd][0]]; 80 if( pos<=ls ) { 81 nd = son[nd][0]; 82 } else if( pos>=ls+2 ) { 83 nd = son[nd][1]; 84 pos -= ls+1; 85 } else { 86 break; 87 } 88 } 89 return nd; 90 } 91 int build( int lf, int rg, int p, char *str ) { // [lf,rg] 92 if( lf>rg ) return 0; 93 if( lf==rg ) return newnode( str[lf], p ); 94 int mid = (lf+rg)>>1; 95 int nd = newnode( str[mid], p ); 96 son[nd][0] = build( lf, mid-1, nd, str ); 97 son[nd][1] = build( mid+1, rg, nd, str ); 98 update( nd ); 99 return nd; 100 } 101 void insert( int pos, int n, char *str ) { 102 int lnode = find( pos ); 103 int rnode = find( pos+1 ); 104 splay( lnode, 0 ); 105 splay( rnode, lnode ); 106 int nd = build( 0, n-1, rnode, str ); 107 son[rnode][0] = nd; 108 splay( nd, 0 ); 109 } 110 void erase_subtree( int nd ) { 111 if( !nd ) return; 112 erase_subtree( son[nd][0] ); 113 erase_subtree( son[nd][1] ); 114 trash[++stot] = nd; 115 } 116 void erase( int lf, int rg ) { 117 int lnode = find(lf-1); 118 int rnode = find(rg+1); 119 splay( lnode, 0 ); 120 splay( rnode, lnode ); 121 int nd = son[rnode][0]; 122 son[rnode][0] = 0; 123 erase_subtree( nd ); 124 update( rnode ); 125 splay( rnode, 0 ); 126 } 127 void reverse( int lf, int rg ) { 128 int lnode = find( lf-1 ); 129 int rnode = find( rg+1 ); 130 splay( lnode, 0 ); 131 splay( rnode, lnode ); 132 inv[son[rnode][0]] ^= true; 133 } 134 char get( int pos ) { 135 int nd = find(pos); 136 char ch = val[nd]; 137 splay( nd, 0 ); 138 return ch; 139 } 140 void print( int nd ) { 141 if( !nd ) return; 142 print(son[nd][0]); 143 fprintf( stderr, "%c", val[nd] ); 144 print(son[nd][1]); 145 } 146 }; 147 148 Splay T; 149 int n, cur_pos; 150 int len; 151 char str[maxn]; 152 153 void getstr( int len ) { 154 while( (str[0]=getchar())!=‘\n‘ ); 155 for( int i=0; i<len; i++ ) 156 str[i] = getchar(); 157 } 158 int main() { 159 scanf( "%d", &n ); 160 cur_pos = 1; 161 for( int i=1; i<=n; i++ ) { 162 char ch[100]; 163 int k; 164 scanf( "%s", ch ); 165 //fprintf( stderr, "Process %d: %s\n", i, ch ); 166 switch( ch[0] ) { 167 case ‘M‘: 168 scanf( "%d", &k ); 169 cur_pos = k+1; 170 break; 171 case ‘I‘: 172 scanf( "%d", &len ); 173 getstr(len); 174 T.insert( cur_pos, len, str ); 175 break; 176 case ‘D‘: 177 scanf( "%d", &len ); 178 T.erase( cur_pos+1, cur_pos+len ); 179 break; 180 case ‘R‘: 181 scanf( "%d", &len ); 182 T.reverse( cur_pos+1, cur_pos+len ); 183 break; 184 case ‘G‘: 185 printf( "%c\n", T.get(cur_pos+1) ); 186 break; 187 case ‘P‘: 188 cur_pos--; 189 break; 190 case ‘N‘: 191 cur_pos++; 192 break; 193 } 194 //fprintf( stderr, "Finished, curent state: " ); 195 //T.print(T.root); 196 //fprintf( stderr, "\n" ); 197 //fprintf( stderr, "cur_pos=%d\n\n", cur_pos ); 198 } 199 200 }
原文：http://www.cnblogs.com/idy002/p/4277711.html
