BZOJ1858 序列操作
一堆标记的线段树。
翻过的，没翻过的，都分开记下来。然后还要注意flip标记与set标记的优先级关系和互相之间的影响。然后就完了。
虽说在这个颓废的下午还是花了好一会才调通。
#include <cstdio>
#include <algorithm>
using namespace std;
struct dat {
int l, r, s, t, m;
};
struct seg {
int l, r, f, z;
dat d[2];
seg *ls, *rs;
};
const int maxn = 100009;
seg *rt, *sp;
int n, m, a[maxn];
inline dat sgd(int v, int s = 1) {
dat r;
r. l = s * v;
r. r = s * v;
r. s = s * v;
r. t = s;
r. m = s * v;
return r;
}
inline dat mgd(const dat& a, const dat& b) {
dat r;
r. l = ((a. l == a. t) ? (a. t + b. l) : a. l);
r. r = ((b. r == b. t) ? (b. t + a. r) : b. r);
r. s = max(max(a. s, b. s), a. r + b. l);
r. t = a. t + b. t;
r. m = a. m + b. m;
return r;
}
#define mid(p) ((p->l+p->r)>>1)
inline void update(seg* p) {
if (p-> z > -1) {
p-> d[0] = sgd(p-> z, p-> r - p-> l);
p-> d[1] = sgd(p-> z ^ 1, p-> r - p-> l);
}
else if (p-> l + 1 == p-> r) {
p-> d[0] = sgd(a[p-> l] ^ p-> f);
p-> d[1] = sgd(a[p-> l] ^ p-> f ^ 1);
}
else {
p-> d[p-> f] = mgd(p-> ls-> d[0], p-> rs-> d[0]);
p-> d[p-> f ^ 1] = mgd(p-> ls-> d[1], p-> rs-> d[1]);
}
}
inline void pushDown(seg* p) {
if (p-> f) {
p-> ls-> f ^= 1;
if (p-> ls-> z > -1)
p-> ls-> z ^= 1;
p-> rs-> f ^= 1;
if (p-> rs-> z > -1)
p-> rs-> z ^= 1;
p-> f = 0;
}
if (p-> z > -1) {
p-> ls-> z = p-> z;
p-> rs-> z = p-> z;
p-> z = -1;
}
update(p-> ls);
update(p-> rs);
}
inline seg* sgtBuild(int l, int r) {
seg* p = sp ++;
p-> l = l;
p-> r = r;
p-> f = 0;
p-> z = -1;
if (l + 1 == r) {
p-> d[0] = sgd(a[l]);
p-> d[1] = sgd(a[l] ^ 1);
}
else {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
p-> d[0] = mgd(p-> ls-> d[0], p-> rs-> d[0]);
p-> d[1] = mgd(p-> ls-> d[1], p-> rs-> d[1]);
}
return p;
}
void sgtSet(seg* p, int l, int r, int v) {
if (p-> l == l && p-> r == r)
p-> z = v;
else {
pushDown(p);
if (r <= mid(p))
sgtSet(p-> ls, l, r, v);
else if (l >= mid(p))
sgtSet(p-> rs, l, r, v);
else {
sgtSet(p-> ls, l, mid(p), v);
sgtSet(p-> rs, mid(p), r, v);
}
}
update(p);
}
void sgtRev(seg* p, int l, int r) {
if (p-> l == l && p-> r == r) {
p-> f ^= 1;
if (p-> z > -1)
p-> z ^= 1;
}
else {
pushDown(p);
if (r <= mid(p))
sgtRev(p-> ls, l, r);
else if (l >= mid(p))
sgtRev(p-> rs, l, r);
else {
sgtRev(p-> ls, l, mid(p));
sgtRev(p-> rs, mid(p), r);
}
}
update(p);
}
dat sgtQry(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> d[0];
else if (p-> z > -1)
return sgd(p-> z, r - l);
else {
pushDown(p);
if (r <= mid(p))
return sgtQry(p-> ls, l, r);
else if (l >= mid(p))
return sgtQry(p-> rs, l, r);
else
return mgd(sgtQry(p-> ls, l, mid(p)), sgtQry(p-> rs, mid(p), r));
}
}
void sgtDisp(seg* p, bool r = 0, bool s = 1) {
if (p-> z > -1)
for (int i = p-> l; i < p-> r; ++ i)
printf("%d", p-> z ^ r);
else if (p-> l + 1 == p-> r)
printf("%d", p-> d[0]. s ^ r);
else {
sgtDisp(p-> ls, r ^ p-> f, 0);
sgtDisp(p-> rs, r ^ p-> f, 0);
}
if (s)
putchar(10);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++ i)
scanf("%d", a + i);
sp = new seg[maxn * 3];
rt = sgtBuild(0, n);
while (m --) {
int opt, a, b;
scanf("%d%d%d", &opt, &a, &b);
if (opt <= 1)
sgtSet(rt, a, b + 1, opt);
else if (opt == 2)
sgtRev(rt, a, b + 1);
else {
dat g = sgtQry(rt, a, b + 1);
if (opt == 3)
printf("%d\n", g. m);
else
printf("%d\n", g. s);
}
//sgtDisp(rt);
}
}
