線分樹成断更新裸題hdu 1698 Just a Hook

セグメント更新(通常は初心者にとってはハードル)は、遅延マーク(または怠惰マーク)を使用する必要があります.簡単に言えば、更新するたびに最後まで更新しないで、遅延マークで更新を次回の更新or問い合わせが必要なときに遅延させます.
标题:O(-1)構想:O(-1)線分ツリー機能:update:セグメント置換(query 1回の総区間のみなので1ノードの情報を直接出力できます)

#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 100000
int col[maxn<<2],sum[maxn<<2];
int Pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int build(int l,int r,int rt)
{
    col[rt]=0;
    sum[rt]=1;
    if(l==r) return 0;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    Pushup(rt);
}
int Pushdown(int rt,int k)
{
    if(col[rt])
        {
            col[rt<<1]=col[rt<<1|1]=col[rt];
            sum[rt<<1]=(k-(k>>1))*col[rt];
            sum[rt<<1|1]=(k>>1)*col[rt];
            col[rt]=0;
        }
}
int query(int L,int R,int Z,int l,int r,int rt)
{
    if(L<=l&&r<=R)
        {
            col[rt]=Z;
            sum[rt]=(r-l+1)*Z;
            return 0;
        }
    Pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) query(L,R,Z,lson);
    if(R>m) query(L,R,Z,rson);
    Pushup(rt);
}
int main()
{
    freopen("hdu1698.in","r",stdin);
    freopen("hdu1698.out","w",stdout);
    int ca,i,N,Q,X,Y,Z,j;
    scanf("%d",&ca);
    for(i=1;i<=ca;i++)
        {   
            scanf("%d%d",&N,&Q);
            build(1,N,1);
            for(j=1;j<=Q;j++)
                {
                    scanf("%d%d%d",&X,&Y,&Z);
                    query(X,Y,Z,1,N,1);
                }
            printf("Case %d: The total value of the hook is %d.
",i,sum[1]);
        }
    return 0;
}