Y2y7m @ 2022-02-21 23:53:38
RE+WA,求大佬帮忙调一下啊
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lson 2*i
#define rson 2*i+1
int n,m;
int a[200010];
struct st
{
int l, r;
int sum;
int lazy;
bool lazy2;
int lmax[2],rmax[2],ans[2];
}t[800010];
void pushup(int i)
{
t[i].sum=t[lson].sum+t[rson].sum;
for(int j=0;j<=1;j++)
{
t[i].lmax[j]=t[lson].lmax[j];
if(j==1&&t[lson].sum==(t[lson].r-t[lson].l+1))
t[i].lmax[i] += t[rson].lmax[i];
else if(j==0&&t[lson].sum==0)
t[i].lmax[j] += t[rson].lmax[j];
t[i].rmax[j]=t[rson].rmax[j];
if (j==1&&t[rson].sum==(t[rson].r-t[rson].l+1))
t[i].rmax[j]+=t[lson].rmax[j];
else if(j==0&&t[rson].sum==0)
t[i].rmax[j]+=t[lson].rmax[j];
t[i].ans[j]=t[lson].rmax[i]+t[rson].lmax[j];
t[i].ans[j]=max(t[i].ans[j],t[lson].ans[j]);
t[i].ans[j]=max(t[i].ans[j],t[rson].ans[j]);
t[i].ans[j]=max(t[i].ans[j],t[i].lmax[j]);
t[i].ans[j]=max(t[i].ans[j],t[i].rmax[j]);
}
}
void pushdown(int i)
{
if(t[i].lazy!=-1)
{
t[i].lazy2=0;
t[lson].sum=(t[lson].r-t[lson].l+1)*t[i].lazy;
t[rson].sum=(t[rson].r-t[rson].l+1)*t[i].lazy;
t[lson].lazy=t[rson].lazy=t[i].lazy;
t[lson].lazy2=t[rson].lazy2=0;
t[lson].lmax[t[i].lazy]=t[lson].rmax[t[i].lazy]=t[lson].ans[t[i].lazy]=(t[lson].r-t[lson].l+1);
t[lson].lmax[t[i].lazy^1]=t[lson].rmax[t[i].lazy^1] = t[lson].ans[t[i].lazy^1]=0;
t[rson].lmax[t[i].lazy]=t[rson].rmax[t[i].lazy] = t[rson].ans[t[i].lazy]=(t[rson].r-t[rson].l+1);
t[rson].lmax[t[i].lazy^1] = t[rson].rmax[t[i].lazy ^ 1] = t[rson].ans[t[i].lazy ^ 1] = 0;
t[i].lazy = -1;
}
if(t[i].lazy2)
{
t[lson].sum=(t[lson].r - t[lson].l + 1) - t[lson].sum;
t[rson].sum=(t[rson].r - t[rson].l + 1) - t[rson].sum;
if (t[lson].lazy!=-1) t[lson].lazy ^= 1;
else t[lson].lazy2^=1;
if (t[rson].lazy!=-1) t[rson].lazy ^= 1;
else t[rson].lazy2^=1;
swap(t[lson].ans[0],t[lson].ans[1]);
swap(t[lson].rmax[0], t[lson].rmax[1]);
swap(t[lson].lmax[0], t[lson].lmax[1]);
swap(t[rson].ans[0], t[rson].ans[1]);
swap(t[rson].rmax[0], t[rson].rmax[1]);
swap(t[rson].lmax[0], t[rson].lmax[1]);
t[i].lazy2 = 0;
}
return;
}
void build(int i,int l,int r)
{
t[i].l=l,t[i].r=r,t[i].lazy=-1;
if(l==r)
{
t[i].sum=a[l];
t[i].lmax[a[l]]=t[i].rmax[a[l]]=t[i].ans[a[l]]=1;
return;
}
int mid=(l + r) >> 1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(i);
}
void change(int i, int l, int r, int d)
{
pushdown(i);
if(l<=t[i].l&&t[i].r<=r)
{
if(d==0||d==1)
{
t[i].sum=(t[i].r - t[i].l + 1)*d;
t[i].lazy = d;
t[i].lmax[d] = t[i].rmax[d] = t[i].ans[d] = (t[i].r - t[i].l + 1);
t[i].lmax[d ^ 1] = t[i].rmax[d ^ 1] = t[i].ans[d ^ 1] = 0;
}
else if(d==2)
{
t[i].sum=(t[i].r-t[i].l+1)-t[i].sum;
t[i].lazy2^= 1;
swap(t[i].lmax[0],t[i].lmax[1]);
swap(t[i].rmax[0],t[i].rmax[1]);
swap(t[i].ans[0],t[i].ans[1]);
}
return ;
}
int mid = (t[i].l + t[i].r) >> 1;
if(l<=mid) change(lson, l, r, d);
if(r>mid) change(rson, l, r, d);
}
int query(int i, int l, int r)
{
pushdown(i);
if(l<=t[i].l&&t[i].r<=r)
return t[i].sum;
int ans=0;
if(l<=t[lson].r)
ans+=query(lson, l, r);
if(r>=t[rson].l)
ans+=query(rson, l, r);
return ans;
}
st querylen(int i, int l, int r)
{
if(l<=t[i].l&& t[i].r <= r)
return t[i];
pushdown(i);
if (r<=t[lson].r) return querylen(lson, l, r);
if (l>=t[lson].l) return querylen(rson, l, r);
st t1=querylen(lson, l, r),t2=querylen(rson, l, r);
st t3;
t3.sum=t1.sum+t2.sum;
for(int j=0;j<=1;j++)
{
t3.lmax[j] = t1.lmax[j];
if(j==1 && t1.sum ==t1.r - t1.l + 1)
t3.lmax[j] += t2.lmax[j];
else if(j == 0 && t1.sum == 0)
t3.lmax[j] += t2.lmax[j];
t3.rmax[j] = t2.rmax[j];
if(j==1&&t2.sum==(t2.r-t2.l+1))
t3.rmax[j] += t1.rmax[j];
else if(j== 0 && t2.sum == 0)
t3.rmax[j]+= t1.rmax[j];
t3.ans[j] = t1.rmax[j] + t2.lmax[j];
t3.ans[j] = max(t3.ans[j], t1.ans[j]);
t3.ans[j] = max(t3.ans[j], t2.ans[j]);
t3.ans[j] = max(t3.ans[j], t3.lmax[j]);
t3.ans[j] = max(t3.ans[j], t3.rmax[j]);
}
return t3;
}
signed main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
int op,x,y;
while(m--)
{
cin>>op>>x>>y;
x++,y++;
if(x>y)
swap(x,y);
if(op==0)
change(1,x,y,0);
if(op==1)
change(1,x,y,1);
if(op==2)
change(1,x,y,2);
if(op==3)
printf("%d\n", query(1,x,y));
if(op==4)
printf("%d\n", querylen(1,x,y).ans[1]);
}
return 0;
}
by WaReTle @ 2022-02-22 12:36:26
@Yueyiming
t[i].lmax[i] += t[rson].lmax[i];
and
t[i].ans[j]=t[lson].rmax[i]+t[rson].lmax[j];
不知道有没有别的错