bloodstalk @ 2023-09-28 16:16:09
rt，这是正解的 push_up
il void push_up(int p)
{
tree[p].pre0 = tree[lc].sum1 ? tree[lc].pre0 : tree[lc].sum0 + tree[rc].pre0;
tree[p].pre1 = tree[lc].sum0 ? tree[lc].pre1 : tree[lc].sum1 + tree[rc].pre1;
tree[p].suf0 = tree[rc].sum1 ? tree[rc].suf0 : tree[rc].sum0 + tree[lc].suf0;
tree[p].suf1 = tree[rc].sum0 ? tree[rc].suf1 : tree[rc].sum1 + tree[lc].suf1;
tree[p].sum0 = tree[lc].sum0 + tree[rc].sum0;
tree[p].sum1 = tree[lc].sum1 + tree[rc].sum1;
tree[p].max0 = max(max(tree[lc].max0,tree[rc].max0),tree[lc].suf0+tree[rc].pre0);
tree[p].max1 = max(max(tree[lc].max1,tree[rc].max1),tree[lc].suf1+tree[rc].pre1);
}下面的是 60pts 的 push_up
il void push_up(int p)
{
tree[p].pre0 = tree[lc].sum1 ? tree[lc].pre0 : tree[lc].len + tree[rc].pre0;
tree[p].pre1 = tree[lc].sum0 ? tree[lc].pre1 : tree[lc].len + tree[rc].pre1;
tree[p].suf0 = tree[rc].sum1 ? tree[rc].suf0 : tree[rc].len + tree[lc].suf0;
tree[p].suf1 = tree[rc].sum0 ? tree[rc].suf1 : tree[rc].len + tree[lc].suf1;
tree[p].sum0 = tree[lc].sum0 + tree[rc].sum0;
tree[p].sum1 = tree[lc].sum1 + tree[rc].sum1;
tree[p].max0 = max(max(tree[lc].max0,tree[rc].max0),tree[lc].suf0+tree[rc].pre0);
tree[p].max1 = max(max(tree[lc].max1,tree[rc].max1),tree[lc].suf1+tree[rc].pre1);
}其中，pre0/1 表示的是前缀最长连续 0/1,suf 表示的是后缀最长连续 0/1，sum0/1 表示区间内 sum0/1 的个数，max0/1 表示区间内最长连续 0/1 的个数。
这两个 push_up 的不同仅在更新 pre0/1,suf0/1里三目运算符的后半段。以第一行更新 pre0 为例，让我不理解的是，为什么如果左儿子的 sum1 为 0 时，左儿子的 len 和 sum0 不相等/yun
by bloodstalk @ 2023-09-28 16:17:07
len 代表的是区间长度
by bloodstalk @ 2023-09-28 16:24:43
下面是完整代码，我没有更新 len，仅在 build 的时候进行了计算。
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 2e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int n,m,op,l,r;
bool a[N];
struct node{
int pre0,pre1,suf0,suf1;
int sum0,sum1,max0,max1;
int len,tag,rev;
}tree[N<<2];
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
#define lc (p<<1)
#define rc (p<<1|1)
il void push_up(int p)
{
tree[p].pre0 = tree[lc].sum1 ? tree[lc].pre0 : tree[lc].sum0 + tree[rc].pre0;
tree[p].pre1 = tree[lc].sum0 ? tree[lc].pre1 : tree[lc].sum1 + tree[rc].pre1;
tree[p].suf0 = tree[rc].sum1 ? tree[rc].suf0 : tree[rc].sum0 + tree[lc].suf0;
tree[p].suf1 = tree[rc].sum0 ? tree[rc].suf1 : tree[rc].sum1 + tree[lc].suf1;
tree[p].sum0 = tree[lc].sum0 + tree[rc].sum0;
tree[p].sum1 = tree[lc].sum1 + tree[rc].sum1;
tree[p].max0 = max(max(tree[lc].max0,tree[rc].max0),tree[lc].suf0+tree[rc].pre0);
tree[p].max1 = max(max(tree[lc].max1,tree[rc].max1),tree[lc].suf1+tree[rc].pre1);
}
il node Merge(node l,node r)
{
node ans;
ans.pre0 = l.sum1 ? l.pre0 : l.sum0 + r.pre0;
ans.pre1 = l.sum0 ? l.pre1 : l.sum1 + r.pre1;
ans.suf0 = r.sum1 ? r.suf0 : r.sum0 + l.suf0;
ans.suf1 = r.sum0 ? r.suf1 : r.sum1 + l.suf1;
ans.sum0 = l.sum0 + r.sum0 , ans.sum1 = l.sum1 + r.sum1;
ans.max0 = max(max(l.max0,r.max0),l.suf0+r.pre0);
ans.max1 = max(max(l.max1,r.max1),l.suf1+r.pre1);
return ans;
}
il void Change(int p,int opt)
{
if(opt == 0)
{
tree[p].pre1 = tree[p].suf1 = tree[p].sum1 = tree[p].max1 = 0;
tree[p].pre0 = tree[p].suf0 = tree[p].sum0 = tree[p].max0 = tree[p].len;
tree[p].tag = 0 , tree[p].rev = 0;
}
if(opt == 1)
{
tree[p].pre0 = tree[p].suf0 = tree[p].sum0 = tree[p].max0 = 0;
tree[p].pre1 = tree[p].suf1 = tree[p].sum1 = tree[p].max1 = tree[p].len;
tree[p].tag = 1 , tree[p].rev = 0;
}
if(opt == 2)
{
swap(tree[p].sum0,tree[p].sum1) , swap(tree[p].max0,tree[p].max1);
swap(tree[p].pre0,tree[p].pre1) , swap(tree[p].suf0,tree[p].suf1);
tree[p].rev ^= 1;
}
}
il void push_down(int p,int l,int r)
{
if(tree[p].tag == 0) Change(lc,0) , Change(rc,0);
if(tree[p].tag == 1) Change(lc,1) , Change(rc,1);
if(tree[p].rev == 1) Change(lc,2) , Change(rc,2);
tree[p].tag = -1 , tree[p].rev = 0;
}
il void build(int p,int l,int r)
{
tree[p].tag = -1 , tree[p].rev = 0 , tree[p].len = r-l+1;
if(l == r)
{
int x = a[l];
tree[p] = {x^1,x,x^1,x,x^1,x,x^1,x,1,-1,0};
return ;
}
int mid = (l+r) >> 1;
build(lc,l,mid) , build(rc,mid+1,r);
push_up(p);
}
il void Modify(int p,int l,int r,int nl,int nr,int opt)
{
if(nl <= l && r <= nr) { Change(p,opt); return ; }
push_down(p,l,r);
int mid = (l+r) >> 1;
if(nl <= mid) Modify(lc,l,mid,nl,nr,opt);
if(nr > mid) Modify(rc,mid+1,r,nl,nr,opt);
push_up(p);
}
il node Query(int p,int l,int r,int nl,int nr)
{
node ans;
if(r < nl || l > nr) return {};
if(nl <= l && r <= nr) return tree[p];
push_down(p,l,r);
int mid = (l+r) >> 1;
ans = Merge(Query(lc,l,mid,nl,nr),Query(rc,mid+1,r,nl,nr));
return ans;
}
signed main()
{
n = read() , m = read();
for(re int i=1;i<=n;i++) a[i] = read();
build(1,1,n);
while(m--)
{
op = read() , l = read()+1 , r = read()+1;
if(op <= 2) Modify(1,1,n,l,r,op);
else
{
node T = Query(1,1,n,l,r);
if(op == 3) cout << T.sum1 << "\n";
else cout << T.max1 << "\n";
}
}
return 0;
}by bloodstalk @ 2023-09-28 16:29:50
哦其实是 Merge 里面出了问题，push_up 这两种写法是一样的，但是在 Merge 里不一样/yun
by bloodstalk @ 2023-09-28 16:36:30
在 Merge 里加了这么一句
if(!l.len) return r;
if(!r.len) return l;就过了/hsh，怎么这么玄学的