//0 a b 将[a,b]区间的所有数变为0//1 a b 将[a,b]区间的所有数都变为1//2 a b 将[a,b]区间的所有数0变1,1变0//3 a b 问[a,b]区间的1的个数//4 a b 问[a,b]区间最长的连续1的子段长度//维护ma_l[2] , ma_r[2] , ma[2] ,sum[2]分别为区间左边，右边，最大的连续1和0，，,区间1和0的个数//lazy 为0,1,2分别表示三个操作//lazy push_down的时候需要注意其子节点的lazy是初始状态-1，using namespace std ;const int maxn = struct node{int l ; int r ;int lazy ;int ma_l[2] , ma_r[2] , ma[2] , sum[2] ;}tree[maxn<<2] ;int h[maxn] ;void push_down(int v){if(tree[v].l == tree[v].r)return ;if(tree[v].lazy == 2){if(tree[left].lazy != -1)push_down(left)(tree[left](tree[left].sum[0] , tree[left].sum[1]) ;tree[left].lazy = tree[v].lazy ;if(tree[right].lazy != -1)push_down(right) (tree[right](tree[right].sum[0] , tree[right].sum[1]) ;tree[right].lazy = tree[v].lazy ;}else if(tree[v].lazy != -1){int t = tree[v].lazy ;tree[left].ma_l[t] = tree[left].ma_r[t] = tree[left].ma[t] = tree[left].sum[t] = (tree[left].r – tree[left].l + 1) ;tree[left].ma_l[!t] = tree[left].ma_r[!t] = tree[left].ma[!t] = tree[left].sum[!t] = 0 ;tree[right].ma_l[t] = tree[right].ma_r[t] = tree[right].ma[t] = tree[right].sum[t] = (tree[right].r – tree[right].l + 1) ;tree[right].ma_l[!t] = tree[right].ma_r[!t] = tree[right].ma[!t] = tree[right].sum[!t] = 0 ;tree[left].lazy = tree[right].lazy = tree[v].lazy ;}tree[v].lazy = -1 ;}void push_up(int v){for(int i = 0;i < 2;i++){tree[v].ma_l[i] = tree[left].ma_l[i] ;tree[v].ma_r[i] = tree[right].ma_r[i] ;tree[v].ma[i] = max(max(tree[left].ma[i] , tree[right].ma[i]), tree[left].ma_r[i] + tree[right].ma_l[i]) ;if(tree[v].ma_l[i] == tree[left].r – tree[left].l + 1)tree[v].ma_l[i] += tree[right].ma_l[i] ;if(tree[v].ma_r[i] == tree[right].r – tree[right].l + 1)tree[v].ma_r[i] += tree[left].ma_r[i] ;tree[v].sum[i] = tree[left].sum[i] + tree[right].sum[i] ;}}void build(int l , int r , int v){tree[v].l = l ;tree[v].r = r;tree[v].lazy = -1 ;if(l == r){tree[v].ma[h[l]] = tree[v].ma_l[h[l]] = tree[v].ma_r[h[l]] = tree[v].sum[h[l]] = 1;tree[v].ma[!h[l]] = tree[v].ma_l[!h[l]] = tree[v].ma_r[!h[l]] = tree[v].sum[!h[l]] = 0;return ;}int mid = (l + r) >> 1 ;build(l , mid , left) ;build(mid+1 , r , right) ;push_up(v) ;}int query(int l , int r , int v , int op){if(l <= tree[v].l && tree[v].r <= r){if(op == 3)return tree[v].sum[1];else return tree[v].ma[1] ;}push_down(v) ;int mid = (tree[v].l + tree[v].r) >> 1 ;int ans_1 = 0, ans_2 = 0 , ans = 0;if(l <= mid)ans_1 = query(l , r , left , op) ;if(r > mid)ans_2 = query(l , r , right, op) ;if(op == 3)return ans_1 + ans_2 ;if(mid >=l && mid < r)ans = min(tree[left].ma_r[1] , tree[left].r – l + 1) + min(tree[right].ma_l[1] , r – tree[right].l + 1) ;return max(max(ans_1 , ans_2) , ans) ;}void update(int l , int r , int v , int op){push_down(v) ;if(l <= tree[v].l && tree[v].r <= r){if(op == 2){(tree[v].ma[0] , tree[v].ma[1]) ;swap(tree[v].sum[0] , tree[v].sum[1]) ;tree[v].lazy = op ;}else{for(int i = 0;i < 2;i++)tree[v].ma_l[i] = tree[v].ma[i] = tree[v].ma_r[i] = tree[v].sum[i] = (tree[v].r – tree[v].l + 1)*(op == i ? 1 : 0) ;tree[v].lazy = op ;}return ;}int mid = (tree[v].l + tree[v].r) >> 1 ;if(l <= mid)update(l , r , left ,op) ;if((r > mid))update(l , r , right ,op) ;push_up(v) ;}int main(){//freopen(“in.txt” ,”r” , stdin) ;int T ;int n , m ;scanf(“%d” , &T) ;while(T–){scanf(“%d%d” ,&n , &m) ;for(int i = 1;i <= n;i++)scanf(“%d” , &h[i]) ;build(1 , n , 1) ;int op , a , b ;while(m–){scanf(“%d%d%d” ,&op , &a , &b) ;if(op < 3)update(a + 1, b + 1 , 1 , op) ;else printf(“%d\n” , query(a + 1, b + 1 , 1 , op)) ;}}return 0;}
这里的风景美不胜收，真让人流连忘返。
