E - Just a Hook

题意:
有几根棍子,给出几个区间的操作变成其他属性的棍子,问最后的值是多少

题解:
线段树区间修改

代码:

#include <bits/stdc++.h>

using namespace std;
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1
typedef long long ll;

const int maxn = 1e5 + 10;

ll sum[maxn << 2];
ll lazy[maxn << 2];

void pushup(ll root)
{
    sum[root] = sum[root << 1] + sum[root << 1 | 1];
}

void pushdown(ll root, ll ln, ll rn)
{
    if(lazy[root])
        {
            lazy[root << 1] = lazy[root];
            lazy[root << 1 | 1] = lazy[root];

            sum[root << 1] = lazy[root] * ln;
            sum[root << 1 | 1] = lazy[root] * rn;

            lazy[root] = 0;
        }
}


void build(ll left, ll right, ll root)
{
    if(left == right)
        {
            sum[root] = 1;
            return ;
        }
    ll mid = left + right >> 1;
    build(lson);
    build(rson);
    pushup(root);
}

void update(ll left, ll right, ll root, ll L, ll R, ll c)
{
    if(L <= left && right <= R) 
        {
            sum[root] = c * (right - left + 1);
            lazy[root] = c;
            return;
        }
    ll mid = left + right >> 1;
    pushdown(root, mid - left + 1, right - mid);

    if(L <= mid)
        update(lson, L, R, c);
    if(R > mid)
        update(rson, L, R, c);
    pushup(root);
}



int main()
{
    int t;
    scanf("%d",&t);
    for(int k = 1; k <= t; k ++)
        {
            memset(sum, 0, sizeof(sum)); 
            memset(lazy, 0, sizeof(lazy));
            ll n;
            scanf("%lld",&n);
            build(1, n, 1);
            ll q;
            scanf("%lld",&q);
            while(q --)
                {
                    ll l,r,c;
                    scanf("%lld%lld%lld",&l,&r,&c);
                    update(1,n,1,l,r,c);
                }
            printf("Case %d: The total value of the hook is %lld.\n",k,sum[1]);
        }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注