HDU 1698線分ツリー

1444 ワード

要求:区間改数裸問題.
方法:セグメントツリーテンプレート.
1.線分ツリーテンプレートをセットすればよい.add配列は加算せず、付与されることに注意する.
	#include
	#include
	#include
	#include
	using namespace std;
	int k,n,q,a,b,c;
	int sum[1000005],add[1000005];
	void build(int o,int l,int r)
	{
		int i,j,k;
		int m=(l+r)/2;
		sum[o]=r-l+1;
		if(l>=r)
		  return;
		build(o*2,l,m);
		build(o*2+1,m+1,r);
	}
	void init()
	{
		int i,j,k;
		scanf("%d%d",&n,&q);
		memset(sum,0,sizeof(sum));
		memset(add,0,sizeof(add));
		build(1,1,n);
	}
	void pushdown(int i,int ln,int rn)
	{
		if(add[i]>0)
		{
		 sum[i*2]=add[i]*ln;
		 sum[i*2+1]=add[i]*rn;
		 add[i*2]=add[i];
		 add[i*2+1]=add[i];
		 add[i]=0;	
		}
	}
	void pushup(int i)
	{
		sum[i]=sum[i*2]+sum[i*2+1];
	}
	void update(int i,int L,int R)
	{
		int lc=i*2,rc=i*2+1;
		int M=L+(R-L)/2;
		if(a<=L&&R<=b)//addv      +add 
		{
		  add[i]=c;
		  sum[i]=c*(R-L+1);
		  return;
		}
		pushdown(i,M-L+1,R-M);//  add
		if(a<=M) update(lc,L,M);
		if(b>M) update(rc,M+1,R);
		pushup(i);//  add	
	}
	int main()
	{
	   int i,j,k,t; 
	   scanf("%d",&t);
	   for(i=1;i<=t;i++)
	   {
	   	 init();
	   	 for(j=1;j<=q;j++)
	   	 {
	   	   scanf("%d%d%d",&a,&b,&c);
		   update(1,1,n);
		 }
	   	 printf("Case %d: The total value of the hook is %d.
",i,sum[1]); } }