HDU-4107-Gangster

HDU-4107-Gangster

http://acm.hdu.edu.cn/showproblem.php?pid=4107

线段树的成段更新，这题可以记录一个区间的最大值和最小值，若一个区间的最大值小于p，则增量增加c，若区间的最小值大于等于p，则增量增加2*c，G++超时，C++过了

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define N  200005
struct cam
{
	int x;
	int y;
	int min;
	int max;
	int v;
}list[N*4];
int n,m,p;
int Min(int x,int y)
{
	return x<y?x:y;
}
int Max(int x,int y)
{
	return x>y?x:y;
}
void build(int k,int x,int y)
{
	list[k].x=x;
	list[k].y=y;
	list[k].min=list[k].max=list[k].v=0;
	if(x==y)
	return;
	int mid=(x+y)/2;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
}
void lazy(int k)
{
	int v=list[k].v;
	if(v>0)
	{
		list[k<<1].v+=v;
		list[k<<1].min+=v;
		list[k<<1].max+=v;
		list[k<<1|1].v+=v;
		list[k<<1|1].min+=v;
		list[k<<1|1].max+=v;
		list[k].v=0;
	}
}
void update(int k,int a,int b,int c)
{
	if(list[k].x==a&&list[k].y==b&&(list[k].min>=p||list[k].max<p))
	{
		if(list[k].max<p)
		{
			list[k].v+=c;
			list[k].max+=c;
			list[k].min+=c;
		}
		else
		{
			list[k].v+=c*2;
			list[k].max+=c*2;
			list[k].min+=c*2;
		}
		return;
	}
	if(list[k].v>0)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(a>mid)
	update(k<<1|1,a,b,c);
	else if(b<=mid)
	update(k<<1,a,b,c);
	else
	{
		update(k<<1,a,mid,c);
		update(k<<1|1,mid+1,b,c);
	}
	list[k].max=Max(list[k<<1].max,list[k<<1|1].max);
	list[k].min=Min(list[k<<1].min,list[k<<1|1].min);
}
int query(int k,int id)
{
	if(list[k].x==id&&list[k].y==id) //初始为0，变化值极为当前的值
	return list[k].v;
	if(list[k].v>0)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(id<=mid)
    return query(k<<1,id);
	else
	return query(k<<1|1,id);
}
int main()
{
	int i,a,b,c;
	while(scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		build(1,1,n);
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			update(1,a,b,c);
		}
		for(i=1;i<=n;i++)
		{
			if(i==n)
			printf("%d\n",query(1,i));
			else
			printf("%d ",query(1,i));
		}
	}
	return 0;
}