欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 1698 Just a Hook(lazy)

程序员文章站 2022-06-08 14:09:33
...

HDU 1698 Just a Hook(lazy) HDU 1698 Just a Hook(lazy)

const int N=1e5+5;
 
    int n,m,t;
    int i,j,k;
    //int a[N];
    struct Node
    {
        int l,r;
        int lazy;
        void update(int x)
        {
            lazy=x;
        }
    }node[N<<2];

void build(int l,int r,int id)
{
    node[id].l=l,node[id].r=r;
    node[id].lazy=1;
    if(l==r) return ;
    else {
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
    }
}

void push_down(int id)
{
    int x=node[id].lazy;
    if(x==-1) return ;
    node[id<<1].update(x);
    node[id<<1|1].update(x);
    node[id].lazy=-1;
}

void update(int l,int r,int val,int id)
{
    int L=node[id].l,R=node[id].r;

    if(L>=l && r>=R || node[id].lazy==val){
        node[id].update(val);
        return ;
    } else{
        int mid=L+R>>1;
        push_down(id);
        if(mid>=l) update(l,r,val,id<<1);
        if(r>=mid+1) update(l,r,val,id<<1|1);
    }
}

int query(int id)
{
    int L=node[id].l,R=node[id].r;

    if(node[id].lazy!=-1){
        return node[id].lazy*(R-L+1);
    }
    return query(id<<1)+query(id<<1|1);
}

int main()
{
    //IOS;
    int num=0;
    rush(){
        sdd(n,m);
        build(1,n,1);
        int x,y,z;
        while(m--){
            sddd(x,y,z);
            update(x,y,z,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",++num,query(1));
    }
    //PAUSE;
    return 0;
}

 

相关标签: # 线段树 HDU