HDU 3397 Sequence operation（线段树的区间合并）

﹏ヽ暗。殇╰゛Y 2022-06-11 05:22 210阅读 0赞

lxhgww got a sequence contains n characters which are all '0's or '1's.  
We have five operations here:  
Change operations:  
0 a b change all characters into '0's in \[a , b\]  
1 a b change all characters into '1's in \[a , b\]  
2 a b change all '0's into '1's and change all '1's into '0's in \[a, b\]  
Output operations:  
3 a b output the number of '1's in \[a, b\]  
4 a b output the length of the longest continuous '1' string in \[a , b\]

Input

T(T<=10) in the first line is the case number.  
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).  
The next line contains n characters, '0' or '1' separated by spaces.  
Then m lines are the operations:  
op a b: 0 <= op <= 4 , 0 <= a <= b < n.

Output

For each output operation , output the result.

Sample Input

1
    10 10
    0 0 0 1 1 0 1 0 1 1
    1 0 2
    3 0 5
    2 2 2
    4 0 4
    0 3 6
    2 3 7
    4 2 8
    1 0 5
    0 5 6
    3 3 9

Sample Output

5
    2
    6
    5

题解：

这题又写了我将近一天。。大体思路是自己想的，就是最后的询问处理询问到连续1的时候懵逼了，然后就搜了个大佬的博客，豁然开朗

这是道区间更新的入门题更难一些的题，考察细节处理

题意：

有5中操作

第一个输入数字为0，将区间\[x,y\]内的值置为0

数字为1，将区间\[x,y\]内的所有值置为1；

数字2，将区间\[x,y\]内的属性反转

数字3，求出\[x,y\]内的1的个数

数字4，求出\[x,y\]内的最长连续1的长度

显然，只有4有难度，由于题目中有属性互换这一bug，我们不仅要保存所有1的情况，0的情况也要保存。。然后只要区间合并的入门经验和一点小技巧就可以做出这题了

详细的在代码中解释

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    #define left k*2//左子树
    #define right k*2+1//右子树
    #define M (t[k].l+t[k].r)/2//区间中点
    struct node
    {
        int l,r;
        int maxo,maxz;//分别代表区间中最长的1和0的长度，one和zero嘛qwq
        int num;//表示区间中1的个数
        int lmo,rmo;//表示从左数最长连续1的个数和从右数最长连续0的个数
        int lmz,rmz;//同理表示0的情况
        int tag1,tag2;//tag1为0是代表区间赋值0,1代表区间赋值1，tag2为区间反转标志
    }t[100005*4];
    void pushup(int k)//合并区间。。这里对于已经区间合并入门的很简单理解，没入门的请认真理解，是套路
    {
        t[k].num=t[left].num+t[right].num;
        t[k].lmo=t[left].lmo;
        t[k].rmo=t[right].rmo;
        t[k].lmz=t[left].lmz;
        t[k].rmz=t[right].rmz;
        t[k].maxo=max(max(t[left].maxo,t[right].maxo),t[left].rmo+t[right].lmo);//区间最长1长度为：左子树最长1的长度，右子树最长1长度，  ---->看下面
        t[k].maxz=max(max(t[left].maxz,t[right].maxz),t[left].rmz+t[right].lmz);//左子树从右数最长连续长度加上右子树从左数最长长度，3个中的最大值
        if(t[k].lmo==t[left].r-t[left].l+1)//如果区间左数最大长度和左区间全长相同，即已经满了，加上右区间的左数最大长度
            t[k].lmo+=t[right].lmo;
        if(t[k].rmo==t[right].r-t[right].l+1)//同理处理区间右数最大长度
            t[k].rmo+=t[left].rmo;
        if(t[k].lmz==t[left].r-t[left].l+1)//处理一遍0的情况
            t[k].lmz+=t[right].lmz;
        if(t[k].rmz==t[right].r-t[right].l+1)
            t[k].rmz+=t[left].rmz;
    }
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag1=-1;//置为-1
        t[k].tag2=0;
        if(t[k].l==t[k].r)
        {
            scanf("%d",&t[k].maxo);
            t[k].num=t[k].lmo=t[k].rmo=t[k].maxo;//初始化很好理解
            t[k].maxz=t[k].lmz=t[k].rmz=!t[k].maxo;
            return;
        }
        int mid=(r+l)/2;
        Build(l,mid,left);
        Build(mid+1,r,right);
        pushup(k);//要合并区间
    }
    void SWAP(int k)//下面会用的，当有互换操作时调用的函数，0和1的情况互换
    {
        t[k].num=t[k].r-t[k].l+1-t[k].num;//最长长度减去当前长度为互换后长度
        swap(t[k].maxo,t[k].maxz);
        swap(t[k].lmz,t[k].lmo);
        swap(t[k].rmz,t[k].rmo);
    }
    void pushdown(int k)//更新子区间，向下传递标志
    {
        if(t[k].l==t[k].r)//已经到根节点了
            return;
        if(t[k].tag1!=-1)
        {
            t[left].tag1=t[right].tag1=t[k].tag1;
            t[left].tag2=t[right].tag2=0;//注意要置0，已经赋为0或1了之前的互换标记要去掉
            if(t[k].tag1==0)
            {
                t[left].maxo=t[left].num=t[left].lmo=t[left].rmo=0;//更新子区间的置1情况
                t[left].maxz=t[left].lmz=t[left].rmz=t[left].r-t[left].l+1;
                t[right].maxo=t[right].num=t[right].lmo=t[right].rmo=0;
                t[right].maxz=t[right].lmz=t[right].rmz=t[right].r-t[right].l+1;
            }
            else
            {
                t[left].num=t[left].maxo=t[left].lmo=t[left].rmo=t[left].r-t[left].l+1;//更新子区间的置0情况
                t[left].maxz=t[left].lmz=t[left].rmz=0;
                t[right].num=t[right].maxo=t[right].lmo=t[right].rmo=t[right].r-t[right].l+1;
                t[right].maxz=t[right].lmz=t[right].rmz=0;
            }
            t[k].tag1=-1;
        }
        if(t[k].tag2%2)//因为如果置换2次就不置换了，所以用%2，更新的时候累加就好了，看到别人使用的是异或
        {
            t[right].tag2++;
            t[left].tag2++;
            SWAP(left);//更新子区间
            SWAP(right);
            t[k].tag2=0;
        }
    }
    void update(int l,int r,int k,int d)
    {
        pushdown(k);//向下传递状态
        if(t[k].l==l&&t[k].r==r)
        {
            if(d==0)//更新当前区间，打上标记
            {
                t[k].maxo=t[k].num=t[k].lmo=t[k].rmo=0;
                t[k].maxz=t[k].lmz=t[k].rmz=r-l+1;
                t[k].tag1=0;
            }
            else if(d==1)
            {
                t[k].num=t[k].maxo=t[k].lmo=t[k].rmo=r-l+1;
                t[k].maxz=t[k].lmz=t[k].rmz=0;
                t[k].tag1=1;
            }
            else
            {
                t[k].tag2=1;
                SWAP(k);
            }
            return;
        }
        int mid=M;
        if(r<=mid)
            update(l,r,left,d);
        else if(l>mid)
            update(l,r,right,d);
        else
        {
            update(l,mid,left,d);
            update(mid+1,r,right,d);
        }
        pushup(k);//区间合并
    }
    int query(int l,int r,int k,int d)//询问
    {
        pushdown(k);
        if(l==t[k].l&&r==t[k].r)
        {
            if(d==3)
            {
                return t[k].num;
            }
            else
                return t[k].maxo;
        }
        int mid=M;
        int p;
        if(r<=mid)
            p=query(l,r,left,d);
        else if(l>mid)
            p=query(l,r,right,d);
        else
        {
            if(d==3)
                p=query(l,mid,left,d)+query(mid+1,r,right,d);
            else
            {
                p=max(query(l,mid,left,d),query(mid+1,r,right,d));
                int t1=min(t[left].rmo,mid-l+1);//这里是重点技巧，t1+t2是求出中间部分的连续长度
                int t2=min(t[right].lmo,r-mid);
                p=max(t1+t2,p);
            }
        }
        return p;
    }
    int main()
    {
        int i,j,k,test,n,m,x,y,d;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d%d",&n,&m);
            Build(0,n-1,1);
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&d,&x,&y);
                if(d>=0&&d<=2)
                {
                    update(x,y,1,d);
                }
                else
                {
                    printf("%d\n",query(x,y,1,d));
                }
            }
        }
        return 0;
    }