Midnight_szx @ 2024-01-24 15:34:08
rt,悬一关
#include<bits/stdc++.h>
using namespace std;
struct node{
int sum, ml, mr, ans, ans0, sum0;//s和,ml左最长1,mr右最长1,ans最多连续的1,ans0最多连续的0
int l0, r0;//左右最长0
int tag1;//取反
int tag2;
}t[400005];
int a[100005], n, m;
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void pushup(int p) {
t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
t[p].sum0 = t[ls(p)].sum0 + t[rs(p)].sum0;
t[p].ans = max(max(t[ls(p)].ans, t[rs(p)].ans), t[ls(p)].mr + t[rs(p)].ml);
t[p].ans0 = max(max(t[ls(p)].ans0, t[rs(p)].ans0), t[ls(p)].r0 + t[rs(p)].l0);
t[p].ml = (t[ls(p)].sum == t[ls(p)].ml) ? t[ls(p)].sum + t[rs(p)].ml : t[ls(p)].ml;
t[p].mr = (t[rs(p)].sum == t[rs(p)].mr) ? t[rs(p)].sum + t[ls(p)].mr : t[rs(p)].mr;
t[p].l0 = (t[ls(p)].l0 == t[ls(p)].sum0) ? t[ls(p)].sum0 + t[rs(p)].l0 : t[ls(p)].l0;
t[p].r0 = (t[rs(p)].r0 == t[rs(p)].sum0) ? t[rs(p)].sum0 + t[ls(p)].r0 : t[rs(p)].r0;
}
void pushdown(int l, int r, int p) {
int mid = l + r >> 1;
if(t[p].tag1) {
swap(t[ls(p)].ml, t[ls(p)].l0);
swap(t[ls(p)].mr, t[ls(p)].r0);
swap(t[ls(p)].sum, t[ls(p)].sum0);
swap(t[ls(p)].ans, t[ls(p)].ans0);
swap(t[rs(p)].ml, t[rs(p)].l0);
swap(t[rs(p)].mr, t[rs(p)].r0);
swap(t[rs(p)].sum0, t[rs(p)].sum);
swap(t[rs(p)].ans, t[rs(p)].ans0);
t[p].tag1 = 0;
t[ls(p)].tag1 ^= 1;
t[rs(p)].tag1 ^= 1;
}
if(t[p].tag2 == 0) {
t[ls(p)].ans = t[ls(p)].sum = t[ls(p)].ml = t[ls(p)].mr = 0;
t[rs(p)].ans = t[rs(p)].sum = t[rs(p)].ml = t[rs(p)].mr = 0;
t[ls(p)].ans0 = t[ls(p)].sum0 = t[ls(p)].l0 = t[ls(p)].r0 = mid - l + 1;
t[rs(p)].ans0 = t[rs(p)].sum0 = t[rs(p)].l0 = t[rs(p)].r0 = r - mid;
t[p].tag2 = -1;
t[ls(p)].tag2 = t[rs(p)].tag2 = -1;
}
if(t[p].tag2 == 1) {
t[ls(p)].ans0 = t[ls(p)].sum0 = t[ls(p)].l0 = t[ls(p)].r0 = 0;
t[rs(p)].ans0 = t[rs(p)].sum0 = t[rs(p)].l0 = t[rs(p)].r0 = 0;
t[ls(p)].ans = t[ls(p)].sum = t[ls(p)].ml = t[ls(p)].mr = mid - l + 1;
t[rs(p)].ans = t[rs(p)].sum = t[rs(p)].ml = t[rs(p)].mr = r - mid;
t[p].tag2 = -1;
t[ls(p)].tag2 = t[rs(p)].tag2 = -1;
}
}
void build(int l, int r, int p) {
t[p].tag1 = 0;
t[p].tag2 = -1;
if(l == r) {
t[p].sum = a[l];
t[p].sum0 = !a[l];
t[p].ml = t[p].mr = t[p].ans = a[l];
t[p].l0 = t[p].r0 = t[p].ans0 = !a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
pushup(p);
}
void turn_0(int sl, int sr, int l, int r, int p) {
if(sl <= l and r <= sr) {
t[p].sum = 0;
t[p].ans = 0;
t[p].ans0 = t[p].sum0 = r - l + 1;
t[p].ml = t[p].mr = 0;
t[p].l0 = t[p].r0 = r - l + 1;
t[p].tag2 = 0;
return;
}
pushdown(l, r, p);
int mid = l + r >> 1;
if(mid >= sl) turn_0(sl, sr, l, mid,ls(p));
if(mid < sr) turn_0(sl, sr, mid + 1, r, rs(p));
pushup(p);
}
void turn_1(int sl, int sr, int l, int r, int p) {
if(sl <= l and r <= sr) {
t[p].sum = r - l + 1;
t[p].ans = r - l + 1;
t[p].ans0 = 0;
t[p].sum0 = 0;
t[p].ml = t[p].mr = r - l + 1;
t[p].l0 = t[p].r0 = 0;
t[p].tag1 = 1;
return;
}
pushdown(l, r, p);
int mid = l + r >> 1;
if(mid >= sl) turn_1(sl, sr, l, mid,ls(p));
if(mid < sr) turn_1(sl, sr, mid + 1, r, rs(p));
pushup(p);
}
void trans(int sl, int sr, int l, int r, int p) {
if(sl <= l and r <= sr) {
t[p].tag1 = t[p].tag1 ^ 1;
swap(t[p].ml, t[p].l0);
swap(t[p].mr, t[p].r0);
swap(t[p].sum, t[p].sum0);
swap(t[p].ans, t[p].ans0);
return;
}
pushdown(l, r, p);
int mid = l + r >> 1;
if(mid >= sl) trans(sl, sr, l, mid,ls(p));
if(mid < sr) trans(sl, sr, mid + 1, r, rs(p));
pushup(p);
}
int query_sum(int sl, int sr, int l, int r, int p) {
if(sl <= l and r <= sr)
return t[p].sum;
pushdown(l, r, p);
int mid = l + r >> 1, k = 0;
if(mid >= sl) k += query_sum(sl, sr, l, mid, ls(p));
if(mid < sr) k += query_sum(sl, sr, mid + 1, r, rs(p));
return k;
}
node query(int sl, int sr, int l, int r, int p) {
if(sl <= l and r <= sr)
return t[p];
if(l > sr or r < sl) return (node){0};
pushdown(l, r, p);
int mid = l + r >> 1;
node ll = query(sl, sr, l, mid, ls(p)), rr = query(sl, sr, mid + 1, r, rs(p)), k;
k.sum = ll.sum + rr.sum;
k.ans = max(ll.ans, rr.ans);
k.ans0 = max(ll.ans0, rr.ans0);
k.ml = (mid - l + 1 == ll.sum) ? ll.sum + rr.ml : ll.ml;
k.mr = (r - mid == rr.sum) ? rr.sum + ll.mr : rr.mr;
k.l0 = (mid - l + 1 == ll.sum0) ? ll.sum0 + rr.l0 : ll.l0;
k.r0 = (r - mid == rr.sum0) ? rr.sum0 + ll.r0 : rr.r0;
k.ans = max(k.ans, ll.mr + rr.ml);
k.ans0 = max(k.ans0, ll.r0 + rr.l0);
return k;
}
int main() {
cin>>n>>m;
for(int i = 1; i <= n; i++)
cin>>a[i];
build(1, n, 1);
int op, l, r;
while(m--) {
cin>>op;
cin>>l>>r;
if(op == 0)
turn_0(l, r, 1, n, 1);
if(op == 1)
turn_1(l, r, 1, n, 1);
if(op == 2)
trans(l, r, 1, n, 1);
if(op == 3)
cout<<query_sum(l, r, 1, n, 1)<<'\n';
if(op == 4)
cout<<query(l, r, 1, n, 1).ans<<'\n';
}
return 0;
}
by Midnight_szx @ 2024-01-24 15:35:42
似乎是 query
写错了pwp
by call_of_silence @ 2024-01-24 15:38:19
@Midnight_szx
建议把所有需要合并的地方写成一个merge函数,这样太难调了
by Midnight_szx @ 2024-01-24 15:39:16
@call_of_silence 谔谔但是那样写的不习惯pwp