HDu 4107セグメントツリーセグメント更新

2286 ワード

題意:所与の区間に対して、毎回1つの区間に1つの値を加えて、もし区間の中のあるノードの値がP以上ならば、プラスの値は2を乗じます
作り方:セグメントツリー、現在の区間の最大値、最小値、タグ値の維持
#include<iostream>
#include<cstdio>
#include<memory.h>
#include<algorithm>
using namespace std;
const int maxn=200002;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int n,m,p,Max[maxn<<2],Min[maxn<<2],col[maxn<<2],num[maxn<<2],print[maxn];
void build(int rt,int l,int r)
{
    num[rt]=0;
    Max[rt]=0;
    Min[rt]=0;
    if(l==r)
    {
        print[l]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
}
void pushUP(int rt)
{
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
    Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
}
void pushDOWN(int rt)
{
    if(num[rt])
    {
        Max[rt<<1]+=num[rt];
        Min[rt<<1]+=num[rt];
        Max[rt<<1|1]+=num[rt];
        Min[rt<<1|1]+=num[rt];
        num[rt<<1]+=num[rt];
        num[rt<<1|1]+=num[rt];
        num[rt]=0;
    }
}
void updata(int rt,int l,int r,int a,int b,int c)
{
    if(l>=a&&r<=b)
    {
        if(Max[rt]<p)
        {
            num[rt]+=c;
            Max[rt]+=c;
            Min[rt]+=c;
            return;
        }
        if(Min[rt]>=p)
        {
            num[rt]+=2*c;
            Min[rt]+=2*c;
            Max[rt]+=2*c;
             return ;
        }
    }
    pushDOWN(rt);
    int mid=(l+r)>>1;
    if(mid>=a)
    {
        updata(lson,a,b,c);
    }
    if(mid<b)
    {
        updata(rson,a,b,c);
    }
    pushUP(rt);
}
void query(int rt,int l,int r)
{
    if(l==r)
    {
        print[l]+=num[rt];
        return;
    }
    pushDOWN(rt);
    int mid=(l+r)>>1;
    query(lson);
    query(rson);
}
int main()
{
    int i,j,k,a,b,c;
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        build(1,1,n);
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            updata(1,1,n,a,b,c);
        }
        query(1,1,n);
        printf("%d",print[1]);
        for(i=2;i<=n;i++)
        {
            printf(" %d",print[i]);
        }
        printf("
"); } return 0; }