HDU_3397
感觉这种维护序列的题目就是填代码，把每种操作的模块写好就OK了。更多和区间合并相关的问题可以参考胡浩的博客http://www.notonlysuccess.com/index.php/segment-tree-complete/。
为了方便实现各种操作，可以引入lc[0/1](left contiguous)表示一个区间从左边开始连续最长0/1是多少，rc[0/1](right contiguous)表示一个区间从右边开始连续最长的区间0/1是多少，mc[0/1](max contiguous)表示当前区间最长的0/1是多少，num[0/1]表示当前区间的0/1的数量是多少，to表示区间全部赋值成0/1的延迟标记，rev表示当前区间0、1反置的延迟标记。
当然有些东西比如num只维护一个num[1]也可以，在区间内0、1反置的时候用区间内元素的数量减去num[1]就是新的num[1]了。
#include<stdio.h>
#include<string.h>
#define MAXD 100010
int N, M, mc[2][4 * MAXD], lc[2][4 * MAXD], rc[2][4 * MAXD];
int rev[4 * MAXD], to[4 * MAXD], num[2][4 * MAXD], a[MAXD];
int getmax(int x, int y)
{
return x > y ? x : y;
}
void doswap(int &x, int &y)
{
int t;
t = x, x = y, y = t;
}
void update(int cur, int x, int y)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
for(int i = 0; i < 2; i ++)
{
mc[i][cur] = getmax(mc[i][ls], mc[i][rs]);
mc[i][cur] = getmax(mc[i][cur], rc[i][ls] + lc[i][rs]);
lc[i][cur] = lc[i][ls] + (lc[i][ls] == mid - x + 1 ? lc[i][rs] : 0);
rc[i][cur] = rc[i][rs] + (rc[i][rs] == y - mid ? rc[i][ls] : 0);
num[i][cur] = num[i][ls] + num[i][rs];
}
}
void pushdown(int cur, int x, int y)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
if(to[cur] != -1)
{
rev[ls] = rev[rs] = 0;
to[ls] = to[rs] = to[cur];
mc[0][ls] = lc[0][ls] = rc[0][ls] = num[0][ls] = (to[cur] ? 0 : mid - x + 1);
mc[0][rs] = lc[0][rs] = rc[0][rs] = num[0][rs] = (to[cur] ? 0 : y - mid);
mc[1][ls] = lc[1][ls] = rc[1][ls] = num[1][ls] = (to[cur] ? mid - x + 1: 0);
mc[1][rs] = lc[1][rs] = rc[1][rs] = num[1][rs] = (to[cur] ? y - mid : 0);
to[cur] = -1;
}
if(rev[cur])
{
rev[ls] = (rev[ls] + 1) % 2, rev[rs] = (rev[rs] + 1) % 2;
doswap(mc[0][ls], mc[1][ls]), doswap(lc[0][ls], lc[1][ls]), doswap(rc[0][ls], rc[1][ls]), doswap(num[0][ls], num[1][ls]);
doswap(mc[0][rs], mc[1][rs]), doswap(lc[0][rs], lc[1][rs]), doswap(rc[0][rs], rc[1][rs]), doswap(num[0][rs], num[1][rs]);
rev[cur] = 0;
}
}
void build(int cur, int x, int y)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
to[cur] = -1, rev[cur] = 0;
if(x == y)
{
mc[0][cur] = lc[0][cur] = rc[0][cur] = num[0][cur] = (a[x] ? 0 : 1);
mc[1][cur] = lc[1][cur] = rc[1][cur] = num[1][cur] = (a[x] ? 1 : 0);
return ;
}
build(ls, x, mid);
build(rs, mid + 1, y);
update(cur, x, y);
}
void init()
{
int i, j, k;
scanf("%d%d", &N, &M);
for(i = 0; i < N; i ++)
scanf("%d", &a[i]);
build(1, 0, N - 1);
}
void color(int cur, int x, int y, int s, int t, int c)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
if(x >= s && y <= t)
{
mc[0][cur] = lc[0][cur] = rc[0][cur] = num[0][cur] = (c ? 0 : y - x + 1);
mc[1][cur] = lc[1][cur] = rc[1][cur] = num[1][cur] = (c ? y - x + 1 : 0);
to[cur] = c, rev[cur] = 0;
return ;
}
pushdown(cur, x, y);
if(mid >= s)
color(ls, x, mid, s, t, c);
if(mid + 1 <= t)
color(rs, mid + 1, y, s, t, c);
update(cur, x, y);
}
void dorev(int cur, int x, int y, int s, int t)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
if(x >= s && y <= t)
{
doswap(mc[0][cur], mc[1][cur]), doswap(lc[0][cur], lc[1][cur]), doswap(rc[0][cur], rc[1][cur]), doswap(num[0][cur], num[1][cur]);
rev[cur] = (rev[cur] + 1) % 2;
return ;
}
pushdown(cur, x, y);
if(mid >= s)
dorev(ls, x, mid, s, t);
if(mid + 1 <= t)
dorev(rs, mid + 1, y, s, t);
update(cur, x, y);
}
int calculate(int cur, int x, int y, int s, int t)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1, ans = 0;
if(x >= s && y <= t)
return num[1][cur];
pushdown(cur, x, y);
if(mid >= s)
ans += calculate(ls, x, mid, s, t);
if(mid + 1 <= t)
ans += calculate(rs, mid + 1, y, s, t);
update(cur, x, y);
return ans;
}
int Search(int cur, int x, int y, int s, int t, int p, int &ans)
{
int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;
if(x >= s && y <= t)
{
ans = getmax(ans, mc[1][cur]);
return p ? rc[1][cur] : lc[1][cur];
}
pushdown(cur, x, y);
if(mid >= t)
return Search(ls, x, mid, s, t, 0, ans);
else if(mid + 1 <= s)
return Search(rs, mid + 1, y, s, t, 1, ans);
int ln, rn;
ln = Search(ls, x, mid, s, t, 1, ans), rn = Search(rs, mid + 1, y, s, t, 0, ans);
update(cur, x, y);
if(x >= s && mid <= t)
{
ans = getmax(ans, rn + rc[1][ls]);
return rc[1][ls] == mid - x + 1 ? rn + rc[1][ls] : lc[1][ls];
}
else if(mid + 1 >= s && y <= t)
{
ans = getmax(ans, ln + lc[1][rs]);
return lc[1][rs] == y - mid ? ln + lc[1][rs] : rc[1][rs];
}
else
ans = getmax(ans, ln + rn);
return 0;
}
void solve()
{
int i, j, k, op, x, y, ans;
for(i = 0; i < M; i ++)
{
scanf("%d%d%d", &op, &x, &y);
if(op == 0)
color(1, 0, N - 1, x, y, 0);
else if(op == 1)
color(1, 0, N - 1, x, y, 1);
else if(op == 2)
dorev(1, 0, N - 1, x, y);
else if(op == 3)
printf("%d\n", calculate(1, 0, N - 1, x, y));
else
{
ans = 0;
Search(1, 0, N - 1, x, y, 0, ans);
printf("%d\n", ans);
}
}
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
init();
solve();
}
return 0;
}