Doubeecat @ 2020-10-03 11:10:31
希望有好心人帮忙看看/kel
如果没有也没事
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define ll long long
#define ri register int
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
ri v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int N = 100010;
int n,m,a[N];
struct node {
int l,r;
int sum1,lsum1,rsum1;
int sum0,lsum0,rsum0,tot;
int tag1,tag2;
// tag1:-1 all zero 1 all one 0 none
// tag2:1 reverse 0 no reverse
}tree[N<<2];
void pushup(int p) {//下放标记
tree[p].tot = tree[p<<1].tot + tree[p<<1|1].tot;
tree[p].lsum1 = max(tree[p<<1].lsum1,tree[p<<1].tot + tree[p<<1|1].lsum1);
tree[p].rsum1 = max(tree[p<<1|1].rsum1,tree[p<<1|1].tot + tree[p<<1].rsum1);
tree[p].sum1 = max(max(tree[p<<1].sum1,tree[p<<1|1].sum1),tree[p<<1].rsum1 + tree[p<<1|1].lsum1);
//维护1的最大子段和
tree[p].lsum0 = max(tree[p<<1].lsum0,tree[p<<1].tot + tree[p<<1|1].lsum0);
tree[p].rsum0 = max(tree[p<<1|1].rsum0,tree[p<<1|1].tot + tree[p<<1].rsum0);
tree[p].sum0 = max(max(tree[p<<1].sum0,tree[p<<1|1].sum0),tree[p<<1].rsum0 + tree[p<<1|1].lsum0);
//维护0的最大子段和
return ;
}
void pushdown(int p) {
if (tree[p].tag1) {
if (tree[p].tag1 == -1) {
tree[p<<1].lsum0 = tree[p<<1].rsum0 = tree[p<<1].sum0 = (tree[p<<1].r - tree[p<<1].l + 1);
tree[p<<1|1].lsum0 = tree[p<<1|1].rsum0 = tree[p<<1|1].sum0 = (tree[p<<1|1].r - tree[p<<1|1].l + 1);
tree[p<<1].lsum1 = tree[p<<1].rsum1 = tree[p<<1].sum1 = 0;
tree[p<<1|1].lsum1 = tree[p<<1|1].rsum1 = tree[p<<1|1].sum1 = 0;
tree[p<<1].tag1 = tree[p<<1|1].tag2 = -1;tree[p<<1].tag2 = tree[p<<1|1].tag2 = 0;
tree[p].tag1 = tree[p].tag2 = 0;
//如果区间覆盖成 0 修改
} else {
tree[p<<1].lsum1 = tree[p<<1].rsum1 = tree[p<<1].sum1 = (tree[p<<1].r - tree[p<<1].l + 1);
tree[p<<1|1].lsum1 = tree[p<<1|1].rsum1 = tree[p<<1|1].sum1 = (tree[p<<1|1].r - tree[p<<1|1].l + 1);
tree[p<<1].lsum0 = tree[p<<1].rsum0 = tree[p<<1].sum0 = 0;
tree[p<<1|1].lsum0 = tree[p<<1|1].rsum0 = tree[p<<1|1].sum0 = 0;
tree[p<<1].tag1 = tree[p<<1|1].tag2 = 1;tree[p<<1].tag2 = tree[p<<1|1].tag2 = 0;
tree[p].tag1 = tree[p].tag2 = 0;
//如果区间覆盖成 1 修改
}
}
if (tree[p].tag2) {
//区间反转
//left son
tree[p<<1].tot = (tree[p<<1].r - tree[p<<1].l + 1) - tree[p<<1].tot;
swap(tree[p<<1].lsum0,tree[p<<1].lsum1);
swap(tree[p<<1].rsum0,tree[p<<1].rsum1);
swap(tree[p<<1].sum0,tree[p<<1].sum1);
if (tree[p<<1].tag1 == -1) tree[p<<1].tag1 = 1;
else if (tree[p<<1].tag1 == 1) tree[p<<1].tag1 = -1;
tree[p<<1].tag2 ^= 1;
//right son
tree[p<<1|1].tot = (tree[p<<1|1].r - tree[p<<1|1].l + 1) - tree[p<<1|1].tot;
swap(tree[p<<1|1].lsum0,tree[p<<1|1].lsum1);
swap(tree[p<<1|1].rsum0,tree[p<<1|1].rsum1);
swap(tree[p<<1|1].sum0,tree[p<<1|1].sum1);
if (tree[p<<1|1].tag1 == -1) tree[p<<1|1].tag1 = 1;
else if (tree[p<<1|1].tag1 == 1) tree[p<<1|1].tag1 = -1;
tree[p<<1|1].tag2 ^= 1;
tree[p].tag2 = 0;
}
}
void build(int p,int l,int r) {
tree[p].l = l,tree[p].r = r;
if (l == r) {
tree[p].sum1 = tree[p].lsum1 = tree[p].rsum1 = (a[l] == 1) ? 1 : 0;
tree[p].sum0 = tree[p].lsum0 = tree[p].rsum0 = (a[l] == 0) ? 1 : 0;
//初始化
return ;
}
int mid = (l + r) >> 1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void change0(int p,int x,int y) {
if (tree[p].l >= x && tree[p].r <= y) {
tree[p].lsum0 = tree[p].rsum0 = tree[p].sum0 = (tree[p<<1].r - tree[p<<1].l + 1);
tree[p].lsum1 = tree[p].rsum1 = tree[p].sum1 = 0;
tree[p].tag1 = -1;tree[p].tag2 = 0;
//区间修改为0
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) change0(p<<1,x,y);
if (y > mid) change0(p<<1|1,x,y);
pushup(p);
return ;
}
void change1(int p,int x,int y) {
if (tree[p].l >= x && tree[p].r <= y) {
tree[p].lsum0 = tree[p].rsum0 = tree[p].sum0 = 0;
tree[p].lsum1 = tree[p].rsum1 = tree[p].sum1 = (tree[p<<1].r - tree[p<<1].l + 1);
tree[p].tag1 = 1;tree[p].tag2 = 0;
//区间修改为1
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) change1(p<<1,x,y);
if (y > mid) change1(p<<1|1,x,y);
pushup(p);
return ;
}
void change2(int p,int x,int y) {
if (tree[p].l >= x && tree[p].r <= y) {
tree[p].tot = (tree[p].r - tree[p].l + 1) - tree[p].tot;
swap(tree[p].lsum0,tree[p].lsum1);
swap(tree[p].rsum0,tree[p].rsum1);
swap(tree[p].sum0,tree[p].sum1);
tree[p].tag2 ^= 1;
//区间反转
return ;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) change2(p<<1,x,y);
if (y > mid) change2(p<<1|1,x,y);
pushup(p);
return ;
}
int query1(int p,int x,int y) {
pushdown(p);
if (tree[p].l == x && tree[p].r == y) {
return tree[p].tot;
}
int mid = (tree[p].l + tree[p].r) >> 1,ans = 0;
if (y <= mid) return query1(p<<1,x,y);
else if (x > mid) return query1(p<<1|1,x,y);
else return query1(p<<1,x,mid) + query1(p<<1|1,mid+1,y);
return ans;
//区间求和
}
int query2(int p,int x,int y) {
pushdown(p);
if (tree[p].l == x && tree[p].r == y) {
return tree[p].sum1;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (y <= mid) return query2(p<<1,x,y);
else if (x > mid) return query2(p<<1|1,x,y);
else return max(max(query2(p<<1,x,mid),query2(p<<1|1,mid+1,y)),min(tree[p<<1|1].lsum1,y - mid) + min(tree[p<<1].rsum1,mid - x + 1));
//区间最大字段和
}
signed main() {
read(n,m);
for (int i = 1;i <= n;++i) {
read(a[i]);
}
build(1,1,n);
while (m--) {
int opt,x,y;read(opt,x,y);++x,++y;
if (opt == 0) change0(1,x,y);
if (opt == 1) change1(1,x,y);
if (opt == 2) change2(1,x,y);
if (opt == 3) printf("%d\n",query1(1,x,y));
if (opt == 4) printf("%d\n",query2(1,x,y));
}
return 0;
}