HDU1698 Just a Hook

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698

题目大意：

线段树成段更新，区间求和，一开始setv忘记初始化了。。。WA了好几次

code：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAX=100005;
int _sum=0;
class IntervalTree
{
private:
    int setv[MAX*4];
public:
    int sumv[MAX*4];
    void init()
    {
        memset(sumv,0,sizeof(sumv));
        memset(setv,-1,sizeof(setv));//要记住初始化
    }
    void build(int o,int L,int R)
    {
        if(R==L)
        {
        	sumv[o]=1;
        	setv[o]=1;
        }
        else
        {
            int M=(L+R)/2;
            build(o*2,L,M);
            build(o*2+1,M+1,R);
            setv[o]=-1;
            sumv[o]=sumv[o*2]+sumv[o*2+1];
        }
    }
    void pushdown(int o)
    {
        if(setv[o]>=0)
        {
            setv[o*2]=setv[o*2+1]=setv[o];
            setv[o]=-1;
        }
    }
    void maintain(int o,int L,int R)
    {
        if(R>L)
        {
            sumv[o]=sumv[o*2]+sumv[o*2+1];
        }
        if(setv[o]>=0)
        {
            sumv[o]=setv[o]*(R-L+1);
        }
    }
    void update(int o,int L,int R,int ql,int qr,int v)
    {
        if(ql<=L&&R<=qr)
        {
            setv[o]=v;
        }
        else
        {
            pushdown(o);
            int M=(L+R)/2;
            if(ql<=M)
                update(o*2,L,M,ql,qr,v);
            else
                maintain(o*2,L,M);
            if(qr>M)
                update(o*2+1,M+1,R,ql,qr,v);
            else
                maintain(o*2+1,M+1,R);
        }
        maintain(o,L,R);
    }
    void query(int o,int L,int R,int ql,int qr)
    {
        if(setv[o]>=0)
        {
            _sum+=setv[o]*(min(R,qr)-max(L,ql)+1);
        }
        else
        {
            if(ql<=L&&R<=qr)
            {
                _sum+=sumv[o];
            }
            else
            {
                int M=(L+R)/2;
                if(ql<=M)
                    query(o*2,L,M,ql,qr);
                if(qr>M)
                    query(o*2+1,M+1,R,ql,qr);
            }
        }
    }
};
IntervalTree tree;
int main()
{
    int T;
    while(cin>>T)
    {
        for(int kase=1;kase<=T;kase++)
        {
            int n,m;
            scanf("%d",&n);
            tree.init();
            tree.build(1,1,n);
            scanf("%d",&m);
            _sum=0;
            while(m--)
            {
                int a,b,v;
                scanf("%d%d%d",&a,&b,&v);
                tree.update(1,1,n,a,b,v);
            }
            tree.query(1,1,n,1,n);
            printf("Case %d: The total value of the hook is %d.\n",kase,_sum);
        }
    }
    return 0;
}

HDU1698 Just a Hook,布布扣,bubuko.com

HDU1698 Just a Hook

原文：http://blog.csdn.net/asdfghjkl1993/article/details/24464227