原题
线段树区间修改模版，不会的百度一下线段树懒惰标记！
//hdu 1698 just a hook #include<iostream> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 using namespace std; int n,m,T; int sum[6010000],col[6010000]; void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];} void pushdown(int pos,int len) { if (col[pos]) { col[pos<<1]=col[pos<<1|1]=col[pos]; sum[pos<<1]=col[pos<<1]*(len-(len>>1)); sum[pos<<1|1]=col[pos<<1|1]*(len>>1); col[pos]=0; } } void build(int l,int r,int pos) { col[pos]=0; if(l==r){sum[pos]=1;return;} int m=(l+r)>>1; build(lson);build(rson); pushup(pos); } void update(int L,int R,int add,int l,int r,int pos) { if(L<=l&&r<=R) { col[pos]=add;//只有在更新的时候再打懒惰标记 sum[pos]=col[pos]*(r-l+1); return; } pushdown(pos,r-l+1); int m=(l+r)>>1; if (L<=m) update(L,R,add,lson); if (R>m) update(L,R,add,rson); pushup(pos); } int main() { scanf("%d",&T); for (int k=1;k<=T;k++) { scanf("%d",&n); build(1,n,1); scanf("%d",&m); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); update(a,b,c,1,n,1); } printf("Case %d: The total value of the hook is %d.\n",k,sum[1]); } return 0; }
