UVa 11402 - Ahoy, Pirates!
题目：给定一个01串，对串的某些区间进行：变0、变1、取反和查询操作。
分析：线段树、离散化。经典的线段染色的变形。区间大小1000000，查询操作1000，如果直接建立1000000的区间的线段树，在上面操作会TLE。因为查询只有1000个，那么利用查询的端点将区间划分成最多4001段（每个端点各是一段、相邻端点间的部分各是一段）。对于所有操作，每段都可以看做一个整体。因此，通过离散化可以建立一个4001区间的区间树，树中每个节点代表一个不等长区间。每个节点除了端点值和左右两颗子树指针外还包含：区间中0的个数（sum[0]）、区间中1的个数（sum[1]）以及区间进行的操作（color）。其中区间操作分为：置0（取值0）、置1（取值1）、取反（取值2）和无操作（取值-1）四种。增加这个域是为了避免每次更新要将所有子节点全部更新。有了区间操作域，每次更新到整个节点时（a==Lvalue&&b==Rvalue），把操作到本节点结束，子树不用操作。直到每次更新子区间时，当前区间的状态要转移到两颗子树上（代码中的Deal操作）。每次更新先继承父区间的状态，之后再更新状态保证了操作的先后顺序。Deal具体操作：1.置0，color = 0、sum[1] = 0、sum[0] = 区间大小；2.置1，color = 1、sum[0] = 0、sum[1] = 区间大小；3.取反，swap(sum[0],sum[1])、color = 1-color（如果color == 1则color = 0 、如果color == 0则color = 1、如果color == -1则color = 2、如果color == 2则color = -1都满足上式）。
注意：输入数据中的换行会导致RE，最好用%s读入操作对应的字母。
#include <iostream>#include <cstdlib>#include <ctime>using namespace std;int main(){freopen("data.in","w",stdout);srand(time(NULL));int T = 10;printf("%d\n",T);for ( int t = 0 ; t < T ; ++ t ) {int m = rand()%100+1;int sum = 0;printf("%d\n",m);for ( int i = 0 ; i < m ; ++ i ) {int n = rand()%200+1;int l = rand()%50+1;printf("%d\n",n);for ( int j = 0 ; j < l ; ++ j )printf("%d",rand()%2);printf("\n");sum += n*l;}int q = rand()%1000+1;printf("%d\n",q);for ( int i = 0 ; i < q ; ++ i ) {switch( rand()%4 ) {case 0: printf("F ");break;case 1: printf("E ");break;case 2: printf("I ");break;case 3: printf("S ");break;}int x = rand()%sum;int y = rand()%sum;if ( x > y ) swap( x, y );printf("%d %d\n",x,y);}}return 0;}