HDU 1698線分ツリー
1444 ワード
要求:区間改数裸問題.
方法:セグメントツリーテンプレート.
1.線分ツリーテンプレートをセットすればよい.add配列は加算せず、付与されることに注意する.
方法:セグメントツリーテンプレート.
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]);
}
}