【bzoj1858】[Scoi2010]序列操作 线段树区间合并
题目描述
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 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 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
输入
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作="" <="" div="">
输出
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
样例输入
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
样例输出
5
2
6
5
提示
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
题解
线段树区间合并
裸题，重要的是两种标记冲突的处理：
pushdown时先rever，再change，在rever时把儿子的标记（pushdown时）和自己的标记（update时）也翻转了。
可以想到，如果题目中是先rever再change，则不会有影响。
如果题目中是先change再rever，则再update函数中直接将change标记改变，也相当于没有任何变化。
标记遇到标记等等，同理。
还有，(-1)^1!=-1。如果按照我的代码，tag数组里0是变成0,1是变成1,-1是不变，那么一定要在rever改变标记时注意是否有change标记。
然后这题就变成了水题。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
int sum[400001][2] , tag[400001] , rev[400001] , ln[400001][2] , rn[400001][2] , tn[400001][2];
void pushup(int l , int r , int x)
{
int mid = (l + r) >> 1 , i;
for(i = 0 ; i <= 1 ; i ++ )
{
sum[x][i] = sum[x << 1][i] + sum[x << 1 | 1][i];
tn[x][i] = max(rn[x << 1][i] + ln[x << 1 | 1][i] , max(tn[x << 1][i] , tn[x << 1 | 1][i]));
ln[x][i] = (ln[x << 1][i] == mid - l + 1) ? ln[x << 1][i] + ln[x << 1 | 1][i] : ln[x << 1][i];
rn[x][i] = (rn[x << 1 | 1][i] == r - mid) ? rn[x << 1 | 1][i] + rn[x << 1][i] : rn[x << 1 | 1][i];
}
}
void pushdown(int l , int r , int x)
{
int mid = (l + r) >> 1;
if(rev[x])
{
swap(sum[x << 1][0] , sum[x << 1][1]);
swap(sum[x << 1 | 1][0] , sum[x << 1 | 1][1]);
swap(ln[x << 1][0] , ln[x << 1][1]);
swap(ln[x << 1 | 1][0] , ln[x << 1 | 1][1]);
swap(rn[x << 1][0] , rn[x << 1][1]);
swap(rn[x << 1 | 1][0] , rn[x << 1 | 1][1]);
swap(tn[x << 1][0] , tn[x << 1][1]);
swap(tn[x << 1 | 1][0] , tn[x << 1 | 1][1]);
if(tag[x << 1] != -1) tag[x << 1] ^= 1;
if(tag[x << 1 | 1] != -1) tag[x << 1 | 1] ^= 1;
rev[x << 1] ^= 1;
rev[x << 1 | 1] ^= 1;
rev[x] = 0;
}
if(tag[x] != -1)
{
sum[x << 1][tag[x]] = ln[x << 1][tag[x]] = rn[x << 1][tag[x]] = tn[x << 1][tag[x]] = mid - l + 1;
sum[x << 1][tag[x] ^ 1] = ln[x << 1][tag[x] ^ 1] = rn[x << 1][tag[x] ^ 1] = tn[x << 1][tag[x] ^ 1] = 0;
sum[x << 1 | 1][tag[x]] = ln[x << 1 | 1][tag[x]] = rn[x << 1 | 1][tag[x]] = tn[x << 1 | 1][tag[x]] = r - mid;
sum[x << 1 | 1][tag[x] ^ 1] = ln[x << 1 | 1][tag[x] ^ 1] = rn[x << 1 | 1][tag[x] ^ 1] = tn[x << 1 | 1][tag[x] ^ 1] = 0;
tag[x << 1] = tag[x << 1 | 1] = tag[x];
tag[x] = -1;
}
}
void build(int l , int r , int x)
{
if(l == r)
{
int t;
scanf("%d" , &t);
sum[x][t] = ln[x][t] = rn[x][t] = tn[x][t] = 1;
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(l , r , x);
}
void update(int b , int e , int a , int l , int r , int x)
{
if(b <= l && r <= e)
{
if(a == 2)
{
swap(sum[x][0] , sum[x][1]);
swap(ln[x][0] , ln[x][1]);
swap(rn[x][0] , rn[x][1]);
swap(tn[x][0] , tn[x][1]);
if(tag[x] != -1) tag[x] ^= 1;
rev[x] ^= 1;
}
else
{
sum[x][a] = ln[x][a] = rn[x][a] = tn[x][a] = r - l + 1;
sum[x][a ^ 1] = ln[x][a ^ 1] = rn[x][a ^ 1] = tn[x][a ^ 1] = 0;
tag[x] = a;
}
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , a , lson);
if(e > mid) update(b , e , a , rson);
pushup(l , r , x);
}
int querysum(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e)
return sum[x][1];
pushdown(l , r , x);
int mid = (l + r) >> 1 , ans = 0;
if(b <= mid) ans += querysum(b , e , lson);
if(e > mid) ans += querysum(b , e , rson);
return ans;
}
int querytot(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e)
return tn[x][1];
pushdown(l , r , x);
int mid = (l + r) >> 1 , ansl , ansr , ansm;
if(e <= mid) return querytot(b , e , lson);
else if(b > mid) return querytot(b , e , rson);
else
{
ansl = querytot(b , e , lson);
ansr = querytot(b , e , rson);
ansm = min(mid - b + 1 , rn[x << 1][1]) + min(e - mid , ln[x << 1 | 1][1]);
return max(max(ansl , ansr) , ansm);
}
}
int main()
{
int n , m , p , x , y;
scanf("%d%d" , &n , &m);
memset(tag , -1 , sizeof(tag));
build(1 , n , 1);
while(m -- )
{
scanf("%d%d%d" , &p , &x , &y);
x ++ ;
y ++ ;
if(p <= 2) update(x , y , p , 1 , n , 1);
else if(p == 3) printf("%d
" , querysum(x , y , 1 , n , 1));
else printf("%d
" , querytot(x , y , 1 , n , 1));
}
return 0;
}