HDu 4107セグメントツリーセグメント更新
題意:所与の区間に対して、毎回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;
}