hdu4107Gangster 线段树

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/4107/

题目给定一个初始值都是零的序列，操作只有一种，就是给一个区间加上一个数，但是当一个数大于等于给定的P的时候就会在这个数上加上两倍的C，否则加上一倍的C。对于这种区间修改以及最终查询的问题我们首要想到的就是线段树，但是如果每次都到达点信息时才进行修改就时间复杂度太高了。对于一个区间中的数，我们可以维护最大值和最小值，只要最小值大于等于P，那么就所有的值都是大于等于P的，对他们的加法tag进行操作即可，对于一个区间，如果最大值小于P，则所有的数都是小于等于P的，对这个区间的tag加上C即可，更新时如果区间不满足在这个性质则需要继续向下更新。这题中只需要tag即可，最后加法tag全部推到最底层进行递归输出。

代码如下：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef unsigned int ui;
  4 typedef long long ll;
  5 typedef unsigned long long ull;
  6 #define pf printf
  7 #define mem(a,b) memset(a,b,sizeof(a))
  8 #define prime1 1e9+7
  9 #define prime2 1e9+9
 10 #define pi 3.14159265
 11 #define lson l,mid,rt<<1
 12 #define rson mid+1,r,rt<<1|1
 13 #define scand(x) scanf("%llf",&x) 
 14 #define f(i,a,b) for(int i=a;i<=b;i++)
 15 #define scan(a) scanf("%d",&a)
 16 #define mp(a,b) make_pair((a),(b))
 17 #define P pair<int,int>
 18 #define dbg(args) cout<<#args<<":"<<args<<endl;
 19 #define inf 0x3f3f3f3f
 20 const int maxn=200010;
 21 int n,m,t;
 22 struct node{
 23     int ans,min,max;//维护最大最小值、加数lazytag 
 24 }p[maxn<<2];
 25 void pushup(int rt)
 26 {
 27     p[rt].max=max(p[rt<<1].max,p[rt<<1|1].max);
 28     p[rt].min=min(p[rt<<1].min,p[rt<<1|1].min);
 29 }
 30 void pushdown(int rt)
 31 {
 32     if(p[rt].ans)
 33     {
 34         p[rt<<1].ans+=p[rt].ans;
 35         p[rt<<1].max+=p[rt].ans;
 36         p[rt<<1].min+=p[rt].ans;
 37         p[rt<<1|1].ans+=p[rt].ans;
 38         p[rt<<1|1].min+=p[rt].ans;
 39         p[rt<<1|1].max+=p[rt].ans;
 40         p[rt].ans=0;
 41     }
 42  } 
 43 void build(int l,int r,int rt)
 44 {
 45     p[rt].min=0;
 46     p[rt].max=0;
 47     p[rt].ans=0;//每个子段的值都要设置 
 48     if(l==r)return;
 49     int mid=l+r>>1;
 50     build(lson);
 51     build(rson);
 52     pushup(rt);
 53 }
 54 void update(int l,int r,int rt,int L,int R,int C)
 55 {
 56     if(L<=l&&r<=R&&(p[rt].min>=t||p[rt].max<t))
 57     {
 58         if(p[rt].min>=t)
 59         {
 60             p[rt].ans+=C*2;//只对标签进行操作 
 61             p[rt].max+=C*2;
 62             p[rt].min+=C*2;
 63             return;
 64         }
 65         else 
 66         {
 67             p[rt].ans+=C;
 68             p[rt].max+=C;
 69             p[rt].min+=C;
 70             return;
 71         }
 72     }
 73     
 74     pushdown(rt);
 75     int mid=l+r>>1;
 76     if(L<=mid)update(lson,L,R,C);
 77     if(R>mid)update(rson,L,R,C);
 78     pushup(rt);
 79 }
 80 void print(int l,int r,int rt)
 81 {
 82     int mid=l+r>>1;
 83     if(l==r)
 84     {
 85         if(l==1)pf("%d",p[rt].ans);
 86         else pf(" %d",p[rt].ans);
 87         return ;
 88     }
 89     pushdown(rt);
 90     print(lson);
 91     print(rson);
 92 }
 93 int main()
 94 {
 95     //freopen("input.txt","r",stdin);
 96     //freopen("output.txt","w",stdout);    
 97     int l,r,c;
 98     while(scanf("%d%d%d",&n,&m,&t)!=EOF)
 99     {
100     
101         build(1,n,1);
102         while(m--)
103         {
104             scanf("%d%d%d",&l,&r,&c);
105             update(1,n,1,l,r,c);
106         }
107         print(1,n,1);
108         pf("
");
109     }
110  }