线段树 Just a hook

怎么说。。暑假集训的数据结构，包括线段树。。然后到现在线段树很久没敲了，结果武汉校赛一道线段树没写出来坑了队友。。然后。。重新复习一遍吧。。线段树的代码风格也定下来了。。

E - Just a Hook

  HDU - 1698  #include<bits/stdc++.h> using namespace std; const int MAXN=100005; #define lson k<<1 #define rson k<<1|1 struct tree { int l,r; int sum; int tag; int mid(){ return (l+r)>>1; } }node[MAXN<<2]; void pushup(int k) { node[k].sum=node[lson].sum+node[rson].sum; } void pushdown(int k,int m) { if(node[k].tag) { node[lson].tag=node[k].tag; node[rson].tag=node[k].tag; node[lson].sum=node[k].tag*(m-(m>>1)); node[rson].sum=node[k].tag*(m>>1); node[k].tag=0; } } void build(int l,int r,int k) { node[k].l=l; node[k].r=r; node[k].tag=0; node[k].sum=1; if(l==r) return ; int mid=node[k].mid(); build(l,mid,lson); build(mid+1,r,rson); pushup(k); } void update(int l,int r,int col,int k) { int m=node[k].r-node[k].l+1; if(l<=node[k].l&&r>=node[k].r) { node[k].tag=col; node[k].sum=m*col; return ; } pushdown(k,m); int mid=node[k].mid(); if(l>mid) update(l,r,col,rson); else if(r<=mid) update(l,r,col,lson); else { update(l,mid,col,lson); update(mid+1,r,col,rson); } pushup(k); } int main() { int t; int ca=1; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int q; build(1,n,1); scanf("%d",&q); while(q--) { int l,r,v; scanf("%d %d %d",&l,&r,&v); update(l,r,v,1); } printf("Case %d: The total value of the hook is %d.\n",ca++,node[1].sum); } return 0; }