一点点想当然的想法使得我WA了6次...
对线段树的理解又深了一点。
熟悉了加标记的操作。
#include<iostream>
#include<cstdio>
#define MAXN 111111
using namespace std;int tree[MAXN<<2];
int flag[MAXN<<2];void PushUp( int rt ){tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}void PushDown( int l,int r,int rt )
{if( flag[rt] ){int m=(r+l)>>1;flag[rt<<1]=flag[rt<<1|1]=flag[rt];//tree[rt<<1]=tree[rt]*(m-l+1)/(r-l+1);tree[rt<<1]=flag[rt]*(m-l+1);//tree[rt<<1]=flag[rt]*(m-(m>>1));//tree[rt<<1|1]=tree[rt]*(r-m)/(r-l+1);tree[rt<<1|1]=flag[rt]*(r-m);//tree[rt<<1|1]=flag[rt]*(m>>1);flag[rt]=0;}
}void build( int l,int r,int rt )
{flag[rt]=0;tree[rt]=1;if( l==r )return ;int m=(l+r)>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );PushUp(rt);
}void update( int L,int R,int v,int l,int r,int rt )
{if( L<=l&&r<=R ){tree[rt]=(r-l+1)*v;flag[rt]=v;return ;}PushDown(l,r,rt);int m=(l+r)>>1;if( L<=m )update( L,R,v,l,m,rt<<1 );if( m+1<=R )update( L,R,v,m+1,r,rt<<1|1 );/**else{ update( L,R,v,l,m,rt<<1 );update( L,R,v,m+1,r,rt<<1|1 );}*/PushUp(rt);
}int main()
{int T,cases=1;scanf( "%d",&T );while( T-- ){memset( flag,0,sizeof(flag) );int N;scanf( "%d",&N );build( 1,N,1 );int Q;scanf( "%d",&Q );int x,y,z;while( Q-- ){scanf( "%d %d %d",&x,&y,&z );update( x,y,z,1,N,1 );//printf( "%d\n",tree[1] );}printf( "Case %d: The total value of the hook is %d.\n",cases++,tree[1] );}return 0;
}