2015
04-14

# Black And White

There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

4
1 0 1 0
5
0 1 4
1 2 3
0 1 4
1 3 3
0 4 4

1
2
0

bl,br,ba 分别表示包括左端点黑石子的连续长度,包括右端点黑石子的连续长度,区间中黑石子的最大连续长度
wl,wr,wa 分别表示包括左端点白石子的连续长度,包括右端点白石子的连续长度,区间中白石子的最大连续长度
ta 表示结点的子结点是否需要更新

首先找到线段树中相应的区间，将黑变白、白变黑实际上就是把 bl,br,ba 和 wl,wr,wa 互换。但是不对这个区间的子区间再进行更新(如果这样做的话时间复杂度就会达到O(n))，而是将 ta xor 1，记下该区间的子区间没有被跟新，下次如果用到(更新或者查询)该区间的子区间再对其进行更新。对包含被更新区间的所有区间进行更新。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 100005;

struct Node {
int l, r;
int bl, br, ba;
int wl, wr, wa;
int ta;
} st[N*3];

int ary[N];

void Update(int p) {
int lp = p * 2, rp = p * 2 + 1;

if ((st[p].ba = max(st[lp].ba, st[rp].ba)) < st[lp].br + st[rp].bl)
st[p].ba = st[lp].br + st[rp].bl;
if ((st[p].wa = max(st[lp].wa, st[rp].wa)) < st[lp].wr + st[rp].wl)
st[p].wa = st[lp].wr + st[rp].wl;
int ll = st[lp].r - st[lp].l + 1, rl = st[rp].r - st[rp].l + 1;
st[p].bl = st[lp].bl; if (st[lp].bl == ll) st[p].bl += st[rp].bl;
st[p].wl = st[lp].wl; if (st[lp].wl == ll) st[p].wl += st[rp].wl;
st[p].br = st[rp].br; if (st[rp].br == rl) st[p].br += st[lp].br;
st[p].wr = st[rp].wr; if (st[rp].wr == rl) st[p].wr += st[lp].wr;
}

void Change(int p) {
swap(st[p].bl, st[p].wl);
swap(st[p].br, st[p].wr);
swap(st[p].ba, st[p].wa);
st[p].ta ^= 1;
}

void Build(int l, int r, int p) {
st[p].l = l; st[p].r = r; st[p].ta = 0;
if (l == r) {
if (ary[l]) {
st[p].bl = st[p].br = st[p].ba = 1;
st[p].wl = st[p].wr = st[p].wa = 0;
} else {
st[p].wl = st[p].wr = st[p].wa = 1;
st[p].bl = st[p].br = st[p].ba = 0;
}
return;
}
int m = (l + r) / 2;
Build(l, m, p * 2);
Build(m + 1, r, p * 2 + 1);
Update(p);
}

void Update(int l, int r, int p) {
if (st[p].l == l && st[p].r == r) {
Change(p);
return;
}
if (st[p].ta) {
Change(p * 2);
Change(p * 2 + 1);
st[p].ta ^= 1;
}
int m = (st[p].l + st[p].r) / 2;
if (r <= m) Update(l, r, p * 2);
else if (l > m) Update(l, r, p * 2 + 1);
else Update(l, m, p * 2), Update(m + 1, r, p * 2 + 1);
Update(p);
}

int Query(int l, int r, int p) {
// printf("%d %d %d\n", p, st[p].ba, st[p].ta);
if (st[p].l == l && st[p].r == r) {
return st[p].ba;
}
if (st[p].ta) {
Change(p * 2);
Change(p * 2 + 1);
st[p].ta ^= 1;
}
int m = (st[p].l + st[p].r) / 2;
if (r <= m) return Query(l, r, p * 2);
else if (l > m) return Query(l, r, p * 2 + 1);
else {
int lr = Query(l, m, p * 2);
int rr = Query(m + 1, r, p * 2 + 1);
return max(max(min(st[p*2].br, lr) + min(st[p*2+1].bl, rr), lr), rr);
}
}

int main() {
int n, m, i, a, b, c;
while (scanf("%d", &n) != EOF) {
for (i = 1; i <= n; i++)
scanf("%d", ary + i);
Build(1, n, 1);
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%d %d %d", &a, &b, &c);
if (a) Update(b, c, 1);
else printf("%d\n", Query(b, c, 1));
}
}
return 0;
}


1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.