題目來源：Sequence operation
題意
給你一個(gè)長度為n的01串移层，現(xiàn)在有m次操作
0 a b表示把區(qū)間[a, b]全部變?yōu)?
1 a b表示把區(qū)間[a, b]全部變?yōu)?
2 a b表示把區(qū)間[a, b]翻轉(zhuǎn)论熙，0變1,1變0
3 a b輸出區(qū)間[a, b]中1的個(gè)數(shù)
4 a b輸出區(qū)間[a, b]中最長連續(xù)的1的長度
思路
用線段樹維護(hù)區(qū)間從左、右開始數(shù)0和1的最大長度万哪，區(qū)間內(nèi)01的最大長度帘撰，區(qū)間內(nèi)1的數(shù)量和區(qū)間是否翻轉(zhuǎn)
由于一個(gè)區(qū)間翻轉(zhuǎn)偶數(shù)次后的結(jié)果和初始結(jié)果一致政钟，所以如果區(qū)間在已有翻轉(zhuǎn)標(biāo)記的情況下再增添一個(gè)翻轉(zhuǎn)標(biāo)記則無需翻轉(zhuǎn)
注意此題需要將pushdown在查詢和更新的最開始處下推蜈敢，不然會(huì)有標(biāo)記推不下去。
代碼
#include <cstdio>
#include <cstring>
#include <iostream>
const int N = 100010;
int a[N];
inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x > y ? y : x; }
namespace SEG
{
struct Tag
{
int lzero, rzero, mzero;
int lone, rone, mone;
int sum;
int lazy, x_or;
} c[N << 2];
inline void pushDown(int k, int l, int r)
{
if (l == r) return;
int mid = (l + r) >> 1;
if (c[k].lazy != -1)
{
c[k << 1].lazy = c[k << 1 | 1].lazy = c[k].lazy;
c[k << 1].x_or = c[k << 1 | 1].x_or = 0;
if (c[k].lazy == 0)
{
c[k << 1].lzero = c[k << 1].rzero = c[k << 1].mzero = mid - l + 1;
c[k << 1].sum = c[k << 1].lone = c[k << 1].rone = c[k << 1].mone = 0;
c[k << 1 | 1].lzero = c[k << 1 | 1].rzero = c[k << 1 | 1].mzero = r - mid;
c[k << 1 | 1].sum = c[k << 1 | 1].lone = c[k << 1 | 1].rone = c[k << 1 | 1].mone = 0;
}
else if (c[k].lazy == 1)
{
c[k << 1].lzero = c[k << 1].rzero = c[k << 1].mzero = 0;
c[k << 1].sum = c[k << 1].lone = c[k << 1].rone = c[k << 1].mone = mid - l + 1;
c[k << 1 | 1].lzero = c[k << 1 | 1].rzero = c[k << 1 | 1].mzero = 0;
c[k << 1 | 1].sum = c[k << 1 | 1].lone = c[k << 1 | 1].rone = c[k << 1 | 1].mone = r - mid;
}
c[k].lazy = -1;
}
if (c[k].x_or)
{
c[k << 1].x_or ^= 1;
c[k << 1 | 1].x_or ^= 1;
std::swap(c[k << 1].lzero, c[k << 1].lone);
std::swap(c[k << 1].rzero, c[k << 1].rone);
std::swap(c[k << 1].mzero, c[k << 1].mone);
c[k << 1].sum = mid - l + 1 - c[k << 1].sum;
std::swap(c[k << 1 | 1].lzero, c[k << 1 | 1].lone);
std::swap(c[k << 1 | 1].rzero, c[k << 1 | 1].rone);
std::swap(c[k << 1 | 1].mzero, c[k << 1 | 1].mone);
c[k << 1 | 1].sum = (r - mid) - c[k << 1 | 1].sum;
c[k].x_or = 0;
}
}
inline void pushUp(int k, int l, int r)
{
int mid = (l + r) >> 1;
c[k].lzero = c[k << 1].lzero;
c[k].rzero = c[k << 1 | 1].rzero;
if (c[k].lzero >= mid - l + 1)
c[k].lzero += c[k << 1 | 1].lzero;
if (c[k].rzero >= r - mid)
c[k].rzero += c[k << 1].rzero;
c[k].mzero = max(c[k << 1].rzero + c[k << 1 | 1].lzero, max(c[k << 1].mzero, c[k << 1 | 1].mzero));
c[k].lone = c[k << 1].lone;
c[k].rone = c[k << 1 | 1].rone;
if (c[k].lone >= mid - l + 1)
c[k].lone += c[k << 1 | 1].lone;
if (c[k].rone >= r - mid)
c[k].rone += c[k << 1].rone;
c[k].mone = max(c[k << 1].rone + c[k << 1 | 1].lone, max(c[k << 1].mone, c[k << 1 | 1].mone));
c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
}
void build(int k, int l, int r)
{
c[k].lazy = -1;
c[k].x_or = 0;
if (l == r)
{
if (a[l] == 0)
{
c[k].lzero = c[k].rzero = c[k].mzero = 1;
c[k].sum = c[k].lone = c[k].rone = c[k].mone = 0;
}
else if (a[l] == 1)
{
c[k].lzero = c[k].rzero = c[k].mzero = 0;
c[k].sum = c[k].lone = c[k].rone = c[k].mone = 1;
}
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
pushUp(k, l, r);
}
// l, r是總區(qū)間 left, right是查詢區(qū)間
int query_sum(int k, int l, int r, int left, int right)
{
pushDown(k, l, r);
if (left <= l && r <= right) return c[k].sum;
int ans = 0;
int mid = (l + r) >> 1;
if (left <= mid) ans += query_sum(k << 1, l, mid, left, right);
if (mid < right) ans += query_sum(k << 1 | 1, mid + 1, r, left, right);
return ans;
}
int query_max(int k, int l, int r, int left, int right)
{
pushDown(k, l, r);
if (left <= l && r <= right) return c[k].mone;
int ans = 0;
int mid = (l + r) >> 1;
if (left <= mid) ans = max(ans, query_max(k << 1, l, mid, left, right));
if (mid < right) ans = max(ans, query_max(k << 1 | 1, mid + 1, r, left, right));
return max(ans, min(c[k << 1].rone, mid - left + 1) + min(c[k << 1 | 1].lone, right - mid));
}
// l, r是總區(qū)間 left, right是查詢區(qū)間殴俱，k是起始節(jié)點(diǎn)編號(hào)政冻，val是更新的值
void update(int k, int l, int r, int left, int right, int val)
{
pushDown(k, l, r);
if (left <= l && r <= right)
{
if (val == 0)
{
c[k].lazy = val;
c[k].lzero = c[k].rzero = c[k].mzero = r - l + 1;
c[k].sum = c[k].lone = c[k].rone = c[k].mone = 0;
}
else if (val == 1)
{
c[k].lazy = val;
c[k].lzero = c[k].rzero = c[k].mzero = 0;
c[k].sum = c[k].lone = c[k].rone = c[k].mone = r - l + 1;
}
else if (val == 2)
{
c[k].x_or = 1;
std::swap(c[k].lzero, c[k].lone);
std::swap(c[k].rzero, c[k].rone);
std::swap(c[k].mzero, c[k].mone);
c[k].sum = (r - l + 1) - c[k].sum;
}
return;
}
int mid = (l + r) >> 1;
if (left <= mid) update(k << 1, l, mid, left, right, val);
if (mid < right) update(k << 1 | 1, mid + 1, r, left, right, val);
pushUp(k, l, r);
}
}
int n, m;
int main()
{
using namespace SEG;
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
memset(c, 0, sizeof(c));
build(1, 1, n);
int op, x, y;
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &op, &x, &y);
x++; y++;
switch (op)
{
case 0:
case 1:
case 2:
update(1, 1, n, x, y, op);
break;
case 3:
printf("%d\n", query_sum(1, 1, n, x, y));
break;
case 4:
printf("%d\n", query_max(1, 1, n, x, y));
break;
default:
break;
}
}
}
return 0;
}
