一道线段树维护区间操作的题 soj4234 01Pairs
【题目链接】
http://cstest.scu.edu.cn/soj/problem.action?id=4234
【题目大意】
给定一个长度为n(n<=10^5)个01序列，定义以下两种操作：
①：将区间[l,r]的序号01翻转，0->1，1->0，如101翻转后为010
②：求区间[l,r]中满足l <= i < j <= r 且 the ith element is 0, jth element is 1
操作次数不超过10^5次。
【分析】
此题维护一个区间上的某些操作，使用线段树比较适合。
对于线段树，通常要维护边界[l,r]。
对于操作②，要求出[l,r]满足其条件的，取mid=(l+r)>>1,query[l,r] = query[l,mid]+query[mid+1,r]+[l,mid]中0的个数*[mid+1]中1的个数。
于是还需要维护一个域存储本区间0的个数，同时存储本区间的query值。
对于操作①，要求出反转区间之后区间域的变化，目测翻转后的值和之前的值并没有太大关系，故增加一个域存储反转后的值，这样反转的时候只需要互换这两个值即可。该域值定义如下：
区间[l,r]中满足l <= i < j <= r 且 the ith element is1, jth element is 0。
同时为了实现惰性操作，还需要一个bool变量rev来标记本区间是否需要反转。
于是维护如下域：
int l , r ; //边界
int zeroCnt ; //[l,r]中0的数目
unsigned int value ; //query的值
unsigned int anti_value ; //反转后的query值
bool rev ; //标记是否需要翻转
【代码】
//2012.11.18 线段树 soj karsbin#include <stdio.h>#include <ctype.h>#include <string.h>const int maxn = 1024 * 100 ;inline bool get(int &t){ bool flag = 0 ; char c; while(!isdigit(c = getchar())&&c!='-') if( c == -1 ) break ; if( c == -1 ) return 0 ; if(c=='-') flag = 1 , t = 0 ; else t = c ^ 48; while(isdigit(c = getchar())) t = (t << 1) + (t << 3) + (c ^ 48) ; if(flag) t = -t ; return 1 ;}struct node { int l , r ;//边界 int zeroCnt ;//[l,r]中0的数目 unsigned int value ;//query的值 unsigned int anti_value ;//反转后的query值 bool rev ;//标记是否需要翻转};node tree[maxn*4] ;int top , n , m , len ;char str[maxn] ;void change(int root){if ( tree[root].l < tree[root].r ){int mid = tree[root*2].r ;tree[root].zeroCnt = tree[root*2].zeroCnt + tree[root*2+1].zeroCnt ;tree[root].value = tree[root*2].value + tree[root*2+1].value + tree[root*2].zeroCnt * (tree[root*2+1].r-mid-tree[root*2+1].zeroCnt) ;tree[root].anti_value = tree[root*2].anti_value + tree[root*2+1].anti_value + (mid-tree[root*2].l+1-tree[root*2].zeroCnt)*tree[root*2+1].zeroCnt ;}}void build(int root,int l,int r){ tree[root].l = l ; tree[root].r = r ; if ( l == r ) { tree[root].zeroCnt = str[l-1] ^ 49 ; tree[root].value = tree[root].anti_value = 0 ; } else { int mid = ( l + r ) >> 1 ; build(root*2, l, mid); build(root*2+1, mid+1, r); change(root); } tree[root].rev = false ;}void modify(int root){ if ( tree[root].rev == true ) { tree[root].zeroCnt = tree[root].r - tree[root].l + 1 - tree[root].zeroCnt ; unsigned int t = tree[root].anti_value ; tree[root].anti_value = tree[root].value ; tree[root].value = t ; if ( tree[root].l < tree[root].r ) { tree[root*2].rev ^= 1 ; tree[root*2+1].rev ^= 1 ; } tree[root].rev = false ; }}unsigned int query(int root,int l,int r,int& zero, int &one){ modify(root); if ( tree[root].l == l && tree[root].r == r ) {zero = tree[root].zeroCnt ;one = tree[root].r - tree[root].l + 1 - zero ; return tree[root].value ; } int mid = ( tree[root].l + tree[root].r ) >> 1 ; unsigned int ans = 0; if( r <= mid ) ans = query(root*2, l, r, zero, one); else if( l > mid ) ans = query(root*2+1, l, r, zero, one); else {int z1, z2 ;int o1, o2 ;ans = query(root*2, l, mid, z1, o1)+query(root*2+1, mid+1, r, z2, o2);zero = z1 + z2 ;one = o1 + o2 ;ans += z1 * o2 ;}modify(root*2);modify(root*2+1); change(root); return ans ;}void reverseSeq(int root,int l,int r){ modify(root); if ( tree[root].l == l && tree[root].r == r ) { tree[root].rev ^= 1 ; modify(root); return ; } int mid = ( tree[root].l + tree[root].r ) >> 1 ; if( r <= mid ) reverseSeq(root*2, l, r); else if( mid < l ) reverseSeq(root*2+1, l, r); else { reverseSeq(root*2, l, mid); reverseSeq(root*2+1, mid+1, r); }modify(root*2);modify(root*2+1); change(root);}int main(){ int t , op , l , r ; get(t); while (t--) { get(n); get(m); scanf("%s",str); build(1,1,strlen(str)); while (m--) { get(op); get(l); get(r); l++;r++; if ( op == 0 ) { reverseSeq(1,l,r); } else {int zero , one ; printf("%u\n",query(1,l,r,zero,one)); } } }}
