HDU 1698 Just a Hook (선분 수)

설명 은 하나의 초기 값 이 1 인 구간 [1, n] 에 대해 일부 구간 업데이트 작업 을 하고 매번 한 구간 [a, b] 의 값 을 c 로 업데이트 합 니 다. 업 데 이 트 된 구간 과 Input 첫 번 째 행위 의 정수 T 는 용례 그룹 수 를 표시 합 니 다. 각 조 의 용례 첫 번 째 행위 의 정수 n 은 구간 이 크 고 작은 것 을 표시 합 니 다. 두 번 째 행위 의 정수 q 는 조작 수 를 표시 합 니 다. 그 다음 에 q 줄 마다 세 개의 정수 a, b, c 는 구간 을 표시 합 니 다.[a, b] 의 값 은 모두 c Output 으로 업 데 이 트 됩 니 다. 각 그룹의 용례 에 대해 출력 업 데 이 트 된 구간 과 Sample Input 1 10 2 1 5 5 9 3 Sample Output Case 1: The totalk value of the hook is 24. Solution 선분 트 리 구간 업데이트 + 구간 조회 코드

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 111111
int t,n,q;
struct Tree
{
    int left,right,data;
}T[4*maxn];
void build(int l,int r,int t)
{
    T[t].left=l;
    T[t].right=r;
    T[t].data=1;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(l,mid,2*t);
    build(mid+1,r,2*t+1);
}
void push_down(int t)
{
    if(T[t].data!=-1)
    {
        T[2*t].data=T[2*t+1].data=T[t].data;
        T[t].data=-1;
    }
}
void update(int l,int r,int z,int t)
{
    if(T[t].left==l&&T[t].right==r||T[t].data==z)
    {
        T[t].data=z;
        return ;
    }
    push_down(t);
    int mid=(T[t].left+T[t].right)>>1;
    if(r<=mid)update(l,r,z,2*t);
    else if(l>mid)update(l,r,z,2*t+1);
    else
    {
        update(l,mid,z,2*t);
        update(mid+1,r,z,2*t+1);
    }
}
int query(int t)
{
    if(T[t].data!=-1)
        return (T[t].right-T[t].left+1)*T[t].data;
    return query(2*t)+query(2*t+1);
}
int main()
{
    int res=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        build(1,n,1);
        while(q--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            update(a,b,c,1);
        }
        int ans=query(1);
        printf("Case %d: The total value of the hook is %d.
",res++,ans);
    }
    return 0;
}