HDU1698

hdu1698.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define sd(x) scanf("%d",&x)
#define sdd(x,y) scanf("%d%d",&x,&y)
#define sddd(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

const int N = 200000+5;

struct node
{
    int left,right,cover;
} tree[3*N];

void update(int i,int l,int r,int c)
{
    int mid;
    if (tree[i].cover==c) return;
    if (tree[i].left==l && tree[i].right==r)
    {
        tree[i].cover=c;
        return;
    }
    if (tree[i].cover!=-1)
    {
        tree[i*2].cover=tree[i].cover;
        tree[i*2+1].cover=tree[i].cover;
        tree[i].cover=-1;
    }
    mid = (tree[i].left+tree[i].right)/2;
    if (mid<=l) return update(i*2+1,l,r,c);
    else if (mid >=r) return update(i*2,l,r,c);
    else
    {
        update(i*2,l,mid,c);
        update(i*2+1,mid,r,c);
    }

}

int  query(int i,int l,int r)
{
    if (tree[i].left==l && tree[i].right==r && tree[i].cover!=-1)
        return tree[i].cover*(r-l);
    int mid=(tree[i].left+tree[i].right)/2;
    if (mid>=r) return query(i*2,l,r);
    else if (mid<=l) return query(i*2+1,l,r);
    else
    {
        return query(i*2,l,mid)+query(i*2+1,mid,r);
    }

}

void build(int i,int l,int r)
{
    tree[i].cover = 1;
    tree[i].left=l;
    tree[i].right=r;
    if (tree[i].right-tree[i].left==1) return;
    int mid = (l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid,r);
}

int main()
{
     //freopen("in.txt","r",stdin);
    //  freopen("out.txt","w",stdout);
    int t,n,q,tcase=0;
    int a,b,c;
    sd(t);
    while(t--)
    {
        sdd(n,q);
        build(1,0,n);
        for (int i=0; i<q; i++)
        {
            sddd(a,b,c);
            update(1,a-1,b,c);
        }
        printf("Case %d: The total value of the hook is %d.\n",++tcase,query(1,0,n));
    }
    return 0;
}