线段树求助

P2572 [SCOI2010] 序列操作

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];

不知道有没有别的错


|