over 3 years ago

线段树的代码题。。写了好久又调了好久
需要注意的是,取反和染色在一个点上只能维护一个,染色的话不能有取反。这样子的话才不会出现问题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 100001
#define c(x) a[x].color
#define rev(x) a[x].rev
using namespace std;
struct node
{
    short rev,color;int one,z0,o1,left0,left1,right0,right1;
} a[maxn*4];
struct point
{
    int left,right,sum,maxx;
    point(int l=0,int r=0,int s=0,int m=0){left=l;right=r;sum=s;maxx=m;}
};
int n,m;
short b[maxn];
inline short reads()
{
    char c=getchar();short bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
inline int readln()
{
    char c=getchar();short bj=1;int result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
inline int max(int x,int y)
{
    if (x>y) return x;return y;
}
inline void pushup(int now,int left,int right)
{
    a[now].one=a[now*2].one+a[now*2+1].one;
    a[now].z0=max(max(a[now*2].z0,a[now*2+1].z0),a[now*2].right0+a[now*2+1].left0);
    a[now].o1=max(max(a[now*2].o1,a[now*2+1].o1),a[now*2].right1+a[now*2+1].left1);
    int lzero=((left+right)>>1)-left+1-a[now*2].one;
    int rzero=right-((left+right)>>1)-a[now*2+1].one;
    a[now].left0=a[now*2].left0;
    if(a[now*2].one==0)a[now].left0+=a[now*2+1].left0;
    a[now].left1=a[now*2].left1;
    if (lzero==0) a[now].left1+=a[now*2+1].left1;
    a[now].right0=a[now*2+1].right0;
    if (a[now*2+1].one==0) a[now].right0+=a[now*2].right0;
    a[now].right1=a[now*2+1].right1;
    if (rzero==0) a[now].right1+=a[now*2].right1;
}
inline void changenode(int now,int x,int y)
{
    a[now].one=a[now].o1=a[now].left1=a[now].right1=x;
    a[now].z0=a[now].left0=a[now].right0=y;
}
inline void reverse(int now,int left,int right)
{
    if (a[now].color!=-1) a[now].color^=1;
    else rev(now)^=1;
    a[now].one=right-left+1-a[now].one;
    swap(a[now].z0,a[now].o1);
    swap(a[now].left0,a[now].left1);
    swap(a[now].right0,a[now].right1);
}
inline void pushdown(int now,int left,int right)
{
    int mid=(left+right)>>1;
    if (c(now)==1)
    {
        c(now*2)=1;rev(now*2)=0;
        changenode(now*2,mid-left+1,0);
        c(now*2+1)=1;rev(now*2+1)=0;
        changenode(now*2+1,right-mid,0);
        c(now)=-1;
    }
    if (c(now)==0)
    {
        c(now*2)=0;rev(now*2)=0;
        changenode(now*2,0,mid-left+1);
        c(now*2+1)=0;rev(now*2+1)=0;
        changenode(now*2+1,0,right-mid);
        c(now)=-1;
    }
    if (a[now].rev)
    {
        a[now].rev=0;
        reverse(now*2,left,mid);
        reverse(now*2+1,mid+1,right);
    }
}
inline void build(int now,int left,int right)
{
    if (left==right)
    {
        a[now].color=-1;
        a[now].rev=0;
        if (b[left]==0)
        {
            a[now].z0=a[now].left0=a[now].right0=1;
            a[now].one=a[now].o1=a[now].left1=a[now].right1=0;
        }
        else
        {
            a[now].z0=a[now].left0=a[now].right0=0;
            a[now].one=a[now].o1=a[now].left1=a[now].right1=1;         
        }
        return;
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
    c(now)=-1;
    pushup(now,left,right);
}
inline void makecolor(int now,int left,int right,int l,int r,int C)
{
    if (l<=left&&r>=right)
    {
        c(now)=C;rev(now)=0;
        if (C) changenode(now,right-left+1,0);
            else changenode(now,0,right-left+1);
        return;
    }
    pushdown(now,left,right);
    int mid=(left+right)>>1;
    if (l<=mid) makecolor(now*2,left,mid,l,r,C);
    if (r>mid) makecolor(now*2+1,mid+1,right,l,r,C);
    pushup(now,left,right);
}
inline void makerev(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r){reverse(now,left,right);return;}
    pushdown(now,left,right);
    int mid=(left+right)>>1;
    if (l<=mid) makerev(now*2,left,mid,l,r);
    if (mid<r) makerev(now*2+1,mid+1,right,l,r);
    pushup(now,left,right);
}
inline int queryone(int now,int left,int right,int l,int r)
{
    if (l<=left&&r>=right)return a[now].one;
    int re=0,mid=(left+right)>>1;
    pushdown(now,left,right);
    if (l<=mid) re+=queryone(now*2,left,mid,l,r);
    if (r>mid)re+=queryone(now*2+1,mid+1,right,l,r);
    return re;
}
inline point query(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r)
    {
        return point(a[now].left1,a[now].right1,right-left+1,a[now].o1);
    }
    int mid=(left+right)>>1;
    point t1,t2;int l1,r1,maxx;
    pushdown(now,left,right);
    if (l<=mid) t1=query(now*2,left,mid,l,r);
    if (mid<r) t2=query(now*2+1,mid+1,right,l,r);
    l1=t1.left;r1=t2.right;
    if (t1.left==t1.sum) l1+=t2.left;
    if (t2.right==t2.sum) r1+=t1.right;
    maxx=max(max(t1.maxx,t2.maxx),t1.right+t2.left);
    return point(l1,r1,t1.sum+t2.sum,maxx);
}
int main()
{
    int i,y,z;short x;
    n=readln();m=readln();
    for (i=1;i<=n;i++) b[i]=reads();
    build(1,1,n);
    for (i=1;i<=m;i++)
    {
        x=reads();y=readln()+1;z=readln()+1;
        if (x==0)
            makecolor(1,1,n,y,z,0);
        if(x==1)
            makecolor(1,1,n,y,z,1);
        if (x==2)
            makerev(1,1,n,y,z);
        if (x==3)
            printf("%d\n",queryone(1,1,n,y,z));
        if (x==4)
        {
            point k=query(1,1,n,y,z);printf("%d\n",k.maxx);
        }
    }
}
← 线段树维护连通性【bzoj1018堵塞的交通&&hdu5068hp&math teacher】 【bzoj2178】【辛普森积分】圆的面积并 →
 
comments powered by Disqus