Hdoj 4107

题目在此

1.       【题意】
2.       n个数，初始都是0，m次更新操作： 
3.       若元素a[i] < p,则a[i]+=c,否则a[i]+=2*c 
4.       最后输出所有的数字
5.       【解题方法】线段树简单区间更新
6.       不过这道题的评测系统貌似坏了吧，代码都是tle。
7. 
   

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int NN = 200010;
struct node{
   int maxx,minn,cover;
}Tree[NN*4];
int n,m,p;
void Push_Up(int rt)
{
    Tree[rt].maxx = max(Tree[rt<<1].maxx,Tree[rt<<1|1].maxx);
    Tree[rt].maxx = min(Tree[rt<<1].minn,Tree[rt<<1|1].minn);
}
void Push_Down(int rt)
{
    if(Tree[rt].cover)
    {
        Tree[rt<<1].cover += Tree[rt].cover;
        Tree[rt<<1|1].cover += Tree[rt].cover;
//        Tree[rt<<1].maxx += Tree[rt].maxx;
//        Tree[rt<<1|1].maxx += Tree[rt].maxx;
//        Tree[rt<<1].minn += Tree[rt].minn;
//        Tree[rt<<1|1].minn += Tree[rt].minn;
        Tree[rt<<1].maxx += Tree[rt].cover;
        Tree[rt<<1|1].maxx += Tree[rt].cover;
        Tree[rt<<1].minn += Tree[rt].cover;
        Tree[rt<<1|1].minn += Tree[rt].cover;
        Tree[rt].cover = 0;
    }
}
void Build(int l,int r,int rt)
{
    Tree[rt].cover=Tree[rt].maxx=Tree[rt].minn=0;
    if(l==r)return ;
    int m = (l+r)>>1;
    Build(l,m,rt<<1);
    Build(m+1,r,rt<<1|1);
}
void Update(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        if(Tree[rt].maxx<p)
        {
            Tree[rt].cover += val;
            Tree[rt].maxx += val;
            Tree[rt].minn += val;
            return ;
        }
        if(Tree[rt].minn>=p)
        {
            Tree[rt].cover += val*2;
            Tree[rt].maxx += val*2;
            Tree[rt].minn += val*2;
            return ;
        }
    }
    else
    {
        Push_Down(rt);
        int m =(l+r)>>1;
        if(L<=m) Update(L,R,val,l,m,rt<<1);
        if(m<R) Update(L,R,val,m+1,r,rt<<1|1);
        Push_Up(rt);
    }
}
void work(int l,int r,int rt)
{
    if(l==r)
    {
        if(l==1)printf("%d",Tree[rt].maxx);
        else printf(" %d",Tree[rt].maxx);
        return ;
    }
    int m = (l+r)>>1;
    Push_Down(rt);
    work(l,m,rt<<1);
    work(m+1,r,rt<<1|1);
}
int main()
{
//    ios::sync_with_stdio();
//    cin.tie(0);
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        Build(1,n,1);
        while(m--)
        {
            int a,b,c;
//            cin>>a>>b>>c;
            scanf("%d%d%d",&a,&b,&c);
            Update(a,b,c,1,n,1);
        }
        work(1,n,1);
        puts("");
    }
    return 0;
}