首页 > ACM题库 > HDU-杭电 > HDU 3397-Sequence operation-线段树-[解题报告]HOJ
2014
03-23

HDU 3397-Sequence operation-线段树-[解题报告]HOJ

Sequence operation

问题描述 :

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]

输入:

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.

输出:

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.

样例输入:

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

样例输出:

5
2
6
5

线段树

题意比较简单,五种操作,两者查询,三种中前两种可看做一种标记,第三种为一种标记,两种标记存在关系,可以保证每个节点通过标记替换达到只存在一种标记:覆盖标记直接覆盖取反操作,取反操作可以变成对覆盖标记取反。区间合并比较麻烦,需要记录0和1的的左右及最大长度,遇上取反操作直接交换0和1的长度,覆盖标记直接取就是。

区间合并时,分三种情况:区间完全在左孩子,区间完全在右孩子,区间在两孩子之间。前两种直接查询,第三种需要区间合并,可记录左孩子的查询区间内的最大值,右孩子在查询区间内的最大值,左孩子右边和右孩子左边的长度的和,三个值中取最大的,即为所需的长度。

printf和scanf明显节省很多时间。

代码较长,写的时候需小心谨慎,容易出现各种低级错误。。。

#include <iostream>

using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
int sum[444444];
int len[2][3][444444];
int op[2][444444];

int max(int a,int b)
{
    return a>b?a:b;
}

void pushup(int l,int r,int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    for (int i=0;i<2;i++)
    {
        if (len[i][0][rt<<1]==(r-l+2)/2)
            len[i][0][rt]=len[i][0][rt<<1]+len[i][0][rt<<1|1];
        else
            len[i][0][rt]=len[i][0][rt<<1];
        if (len[i][2][rt<<1|1]==(r-l+1)/2)
            len[i][2][rt]=len[i][2][rt<<1]+len[i][2][rt<<1|1];
        else
            len[i][2][rt]=len[i][2][rt<<1|1];
        len[i][1][rt]=max(len[i][2][rt<<1]+len[i][0][rt<<1|1],max(len[i][1][rt<<1],len[i][1][rt<<1|1]));
    }
}

void build(int l,int r,int rt)
{
    op[0][rt]=-1;
    op[1][rt]=0;
    if (l==r)
    {
        scanf("%d",&sum[rt]);
        len[1][0][rt]=len[1][1][rt]=len[1][2][rt]=sum[rt];
        len[0][0][rt]=len[0][1][rt]=len[0][2][rt]=1-sum[rt];
        return ;
    }
    delf;
    build(lson);
    build(rson);
    pushup(l,r,rt);
}

void opea(int l,int r,int rt)
{
    if (op[0][rt]!=-1)
        op[0][rt]=1-op[0][rt];
    else
    {
        if (op[1][rt]==1)
            op[1][rt]=0;
        else       
            op[1][rt]=1;  
    } 
    sum[rt]=r-l+1-sum[rt];
    for (int i=0;i<3;i++)
    {
        int t=len[0][i][rt];
        len[0][i][rt]=len[1][i][rt];
        len[1][i][rt]=t;
    }
}

void setupdate(int v,int l,int r,int rt)
{
    sum[rt]=(r-l+1)*v;
    op[1][rt]=0;
    op[0][rt]=v;
    for (int i=0;i<3;i++)
    {
        len[0][i][rt]=(r-l+1)*(1-op[0][rt]);
        len[1][i][rt]=(r-l+1)*op[0][rt];
    }
}

void pushdown(int l,int r,int rt)
{
    if (op[0][rt]>=0)
    {
        delf;
        setupdate(op[0][rt],lson);
        setupdate(op[0][rt],rson);
        op[0][rt]=-1;
    }
    if(op[1][rt])
    {
        delf;
        opea(lson);
        opea(rson);
        op[1][rt]=0;
    } 
}

void update(int L,int R,int k,int l,int r,int rt)
{
    if (L<=l&&r<=R)
    {
        if (k==0||k==1)
            setupdate(k,l,r,rt);
        else
            opea(l,r,rt);
        return ;
    }
    pushdown(l,r,rt);
    delf;
    if (m>=L)
        update(L,R,k,lson);
    if (R>m)
        update(L,R,k,rson);
    pushup(l,r,rt);
}

int query(int L,int R,int l,int r,int rt)
{      
    if (L==l&&r==R)
        return len[1][1][rt];
    pushdown(l,r,rt);   
    delf;
    if (L>m)
        return query(L,R,rson);
    if (R<=m)
        return query(L,R,lson);
    if (L<=m&&R>m)
    {
        int lr = query(L,m,lson);//左子树  
        int rr = query(m+1,R,rson);//右子树  
            //中间  
        int a = len[1][2][rt<<1];//左子树右边最长连续1,注意它的个数不应该大于区间[l,tree[rt<<1].r]的个数   
        if (a>m-L+1)
            a=m-L+1; 
        int b = len[1][0][rt<<1|1];//右子树左边最长连续1,注意它的个数不应该大于区间[tree[rt<<1|1].l,r]的个数  
        if (b>R-m)
            b=R-m;              
        return max(max(lr,rr),a+b);//最后取左子树、右子树和中间三者的最大值       
    }
}

int Query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
        return sum[rt];
    pushdown(l,r,rt);
    delf;
    int s=0;
    if (L<=m)
        s=s+Query(L,R,lson);
    if (R>m)
        s=s+Query(L,R,rson);
    pushup(l,r,rt);
    return s;
}

int main()
{
    int m,n;
    int r;
    scanf("%d",&r);
    while (r--)
    {
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while (m--)
        {
            int k,a,b;
            scanf("%d%d%d",&k,&a,&b);
            if (k<=2)
                update(a+1,b+1,k,1,n,1);
            if (k==3)
                printf("%d\n",Query(a+1,b+1,1,n,1));
            if (k==4)   
                printf("%d\n",query(a+1,b+1,1,n,1));
        }
    } 
}

参考:http://blog.csdn.net/u011663071/article/details/12948991


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept