線分樹成断更新裸題hdu 1698 Just a Hook
セグメント更新(通常は初心者にとってはハードル)は、遅延マーク(または怠惰マーク)を使用する必要があります.簡単に言えば、更新するたびに最後まで更新しないで、遅延マークで更新を次回の更新or問い合わせが必要なときに遅延させます.
标题:O(-1)構想:O(-1)線分ツリー機能:update:セグメント置換(query 1回の総区間のみなので1ノードの情報を直接出力できます)
标题:O(-1)構想:O(-1)線分ツリー機能:update:セグメント置換(query 1回の総区間のみなので1ノードの情報を直接出力できます)
#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 100000
int col[maxn<<2],sum[maxn<<2];
int Pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int build(int l,int r,int rt)
{
col[rt]=0;
sum[rt]=1;
if(l==r) return 0;
int m=(l+r)>>1;
build(lson);
build(rson);
Pushup(rt);
}
int Pushdown(int rt,int k)
{
if(col[rt])
{
col[rt<<1]=col[rt<<1|1]=col[rt];
sum[rt<<1]=(k-(k>>1))*col[rt];
sum[rt<<1|1]=(k>>1)*col[rt];
col[rt]=0;
}
}
int query(int L,int R,int Z,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
col[rt]=Z;
sum[rt]=(r-l+1)*Z;
return 0;
}
Pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) query(L,R,Z,lson);
if(R>m) query(L,R,Z,rson);
Pushup(rt);
}
int main()
{
freopen("hdu1698.in","r",stdin);
freopen("hdu1698.out","w",stdout);
int ca,i,N,Q,X,Y,Z,j;
scanf("%d",&ca);
for(i=1;i<=ca;i++)
{
scanf("%d%d",&N,&Q);
build(1,N,1);
for(j=1;j<=Q;j++)
{
scanf("%d%d%d",&X,&Y,&Z);
query(X,Y,Z,1,N,1);
}
printf("Case %d: The total value of the hook is %d.
",i,sum[1]);
}
return 0;
}