Just a Hook HDU - 1698Just a Hook HDU - 1698 线段树区间替换

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+;

struct node{

    int l,r;

    int sum;

    int add;

}tr[N*];

void pushdown(int root)

{

    if (tr[root].add)

    {

        tr[root<<].add=tr[root].add;

        tr[root<<|].add=tr[root].add;

        int mid=(tr[root].l+tr[root].r)/;

        tr[root<<].sum=tr[root].add*(mid-tr[root].l+);

        tr[root<<|].sum=tr[root].add*(tr[root].r-mid);

        tr[root].add=;

    }

}

void pushup(int u)

{

    tr[u].sum=tr[u<<].sum+tr[u<<|].sum;

}

void build(int root, int l, int r)

{

    tr[root].l=l;

    tr[root].r=r;

    tr[root].add=;

    tr[root].sum=;

    if(l==r)

    {

        tr[root].sum = ;

        return ;

    }

    int mid=l+r>>;

    build(root<<,l,mid);

    build(root<<|,mid+,r);

    pushup(root);

}

void update(int root,int ql,int qr,int c)

{

    if (ql>tr[root].r||qr<tr[root].l)

        return;

    if (ql<=tr[root].l&&tr[root].r<= qr)

    {

        tr[root].sum=(tr[root].r-tr[root].l+)*c;

        tr[root].add=c;

    }

    else

    {

        pushdown(root);

        int mid=tr[root].l+tr[root].r>>;

        update(root<<,ql,qr,c);

        update(root<<|,ql,qr,c);

        pushup(root);

    }

}

int main()

{

    int t,cnt=;

    scanf("%d",&t);

    while(t--)

    {

        int n,q;

        scanf("%d%d",&n,&q);

        build(,,n);

        while(q--)

        {

            int l,r,op;

            scanf("%d%d%d",&l,&r,&op);

            update(,l,r,op);

        }

        printf("Case %d: The total value of the hook is %d.\n", ++cnt, tr[].sum);

    }

}