HDU.1689 Just a Hook (线段树 区间替换 区间总和)

题意分析

一开始叶子节点均为1，操作为将[L,R]区间全部替换成C，求总区间[1，N]和

线段树维护区间和 。

建树的时候初始化为1，更新区间时候放懒惰标记，下推标记更新区间和。

由于是替换，不是累加，所以更新的时候不是+=，而是直接=。

注意这点就可以了，然后就是多组数据注意memset，因为这个WA几发。

代码总览

#include <bits/stdc++.h>

#define maxn 200010

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

int Sum[maxn<<2],Lazy[maxn<<2];

int A[maxn];

void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}

int N,Q,lq,rq,val;

void Build(int l,int r,int rt){

    if(l==r) {

        Sum[rt] = 1;

        return;

    }

    int m=(l+r)>>1;

    Build(l,m,rt<<1);

    Build(m+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int L,int C,int l,int r,int rt){

    if(l==r){

        Sum[rt]+=C;

        return;

    }

    int m=(l+r)>>1;

    if(L <= m) UpdatePoint(L,C,l,m,rt<<1);

    else UpdatePoint(L,C,m+1,r,rt<<1|1);

    PushUp(rt);

}

void PushDown(int rt,int ln,int rn){

    if(Lazy[rt]){

        Lazy[rt<<1] = Lazy[rt];

        Lazy[rt<<1|1] = Lazy[rt];

        Sum[rt<<1] = Lazy[rt]*ln;

        Sum[rt<<1|1] = Lazy[rt]*rn;

        Lazy[rt]=0;

    }

}

void UpdateInterval(int L,int R,int C,int l,int r,int rt){

    if(L <= l && r <= R){

        Sum[rt] = C*(r-l+1);

        Lazy[rt] = C;

        return ;

    }

    int m=(l+r)>>1;

    PushDown(rt,m-l+1,r-m);

    if(L <= m) UpdateInterval(L,R,C,l,m,rt<<1);

    if(R >  m) UpdateInterval(L,R,C,m+1,r,rt<<1|1);

    PushUp(rt);

}

int Query(int L,int R,int l,int r,int rt){

    if(L <= l && r <= R){

        return Sum[rt];

    }

    int m = (l+r)>>1;

    PushDown(rt,m-l+1,r-m);

    int ANS = 0;

    if(L <= m) ANS += Query(L,R,l,m,rt<<1);

    if(R > m) ANS += Query(L,R,m+1,r,rt<<1|1);

    return ANS;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int TestCase;

    scanf("%d",&TestCase);

    for(int i = 1;i<=TestCase;++i){

        scanf("%d",&N);

        memset(Lazy,0,sizeof Lazy);

        Build(1,N,1);

        scanf("%d",&Q);

        for(int j = 0;j<Q;++j){

            scanf("%d %d %d",&lq,&rq,&val);

            UpdateInterval(lq,rq,val,1,N,1);

        }

        int ans =Query(1,N,1,N,1);

        printf("Case %d: The total value of the hook is %d.\n",i,ans);

    }

    return 0;

}