一堆标记的线段树。


翻过的,没翻过的,都分开记下来。然后还要注意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);

}

}