hdu1698 发表于 2018-04-07 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:hdu1698 题解 区间修改线段树模板题,注意输出格式 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i<=y;++i)using namespace std;const int N=1e6;int tr[N<<2],lz[N<<2],n,m,T;inline void pushdown(int o,int l,int r){ if(l==r){tr[o]=lz[o];} lz[o<<1|1]=lz[o<<1]=lz[o]; int mid=l+r>>1; tr[o<<1]=lz[o]*(mid-l+1); tr[o<<1|1]=lz[o]*(r-mid); lz[o]=0;}void build(int o,int l,int r){ if(l==r){tr[o]=1;return ;} int mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); tr[o]=tr[o<<1]+tr[o<<1|1];}void update(int o,int l,int r,int ll,int rr,int c){ if(ll<=l&&rr>=r){lz[o]=c,tr[o]=c*(r-l+1);return ;} if(lz[o])pushdown(o,l,r); int mid=l+r>>1; if(ll<=mid)update(o<<1,l,mid,ll,rr,c); if(rr>mid)update(o<<1|1,mid+1,r,ll,rr,c); tr[o]=tr[o<<1]+tr[o<<1|1];}int main(){ scanf("%d",&T); rep(k,1,T){ memset(lz,0,sizeof(lz)); scanf("%d%d",&n,&m); build(1,1,n); rep(i,1,m){ int a,b,c; scanf("%d%d%d",&a,&b,&c); update(1,1,n,a,b,c); } printf("Case %d: The total value of the hook is %d.\n",k,tr[1]); } return 0;}