1. 题目

传送门= ̄ω ̄=

2. 题解

线段树模板题
区间修改
这应该是目前我打过最好看的线段树了

#include <bits/stdc++.h>
using namespace std;
struct N{int d,l,r,f;N*s[2];N(){d=l=r=f=0,s[0]=s[1]=0;}}*root=0;
void update(N*&a){a->d=a->s[0]->d+a->s[1]->d;}
void pdown(N*&a)
{
    a->s[0]->f=a->f,a->s[0]->d=(a->s[0]->r-a->s[0]->l+1)*a->f;
    a->s[1]->f=a->f,a->s[1]->d=(a->s[1]->r-a->s[1]->l+1)*a->f;
    a->f=0;
}
void build(int l,int r,N*&a)
{
    a=new N,a->l=l,a->r=r;
    if(l==r){a->d=1;return;}
    build(l,(l+r)>>1,a->s[0]),build(((l+r)>>1)+1,r,a->s[1]),update(a);
}
void work(int l,int r,int k,N*&a)
{
    if(l<=a->l&&a->r<=r){a->f=k,a->d=(a->r-a->l+1)*k;return;}
    if(a->f)pdown(a);
    if(l<=((a->l+a->r)>>1))work(l,r,k,a->s[0]);
    if(r>((a->l+a->r)>>1))work(l,r,k,a->s[1]);
    update(a);
}
void del(N*&a){if(a->s[0])del(a->s[0]),del(a->s[1]);delete a;}
int t,n,q;
int main()
{
    scanf("%d",&t);
    for(int cnt=1;cnt<=t;cnt++)
    {
        scanf("%d%d",&n,&q),build(1,n,root);
        for(int i=1,l,r,k;i<=q;i++)scanf("%d%d%d",&l,&r,&k),work(l,r,k,root);
        printf("Case %d: The total value of the hook is %d.\n",cnt,root->d);
        del(root);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

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