HDU - 1698 http://acm.hdu.edu.cn/showproblem.php?pid=1698 思路：区间更新 直接整段区间求和
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100000 + 10; int n,m; struct node { int v,ltag,l,r,len; }tree[maxn << 2]; void iset(int id,int l,int r) { tree[id].l = l; tree[id].r = r; tree[id].ltag = 0; tree[id].v = 1; tree[id].len = r-l+1; } int btree(int l,int r,int id) { iset(id,l,r); if(l == r) return tree[id].v; int mid = l+r>>1; btree(l,mid,id<<1); btree(mid+1,r,id<<1|1); return tree[id].v = tree[id<<1].v + tree[id<<1|1].v; } void uselazy(int lazy,int id) { tree[id].ltag = lazy; tree[id].v = lazy*tree[id].len; } int pushtag(int id) { int k = id; int lazy = tree[id].ltag; if(lazy) { uselazy(lazy,id<<1); uselazy(lazy,id<<1|1); tree[k].ltag = 0; } return 0; } int updata(int ql,int qr,int v,int id) { int l = tree[id].l, r = tree[id].r; if(l == ql && r == qr) {tree[id].ltag = v; return tree[id].v = v*tree[id].len;} pushtag(id); int mid = l+r>>1; if(qr <= mid) updata(ql,qr,v,id<<1); else if(ql > mid) updata(ql,qr,v,id<<1|1); else updata(ql,mid,v,id<<1), updata(mid+1,qr,v,id<<1|1); return tree[id].v = tree[id<<1].v + tree[id<<1|1].v; } int main() { int t; scanf("%d",&t); for(int kase = 1; kase <= t; kase ++) { scanf("%d%d",&n,&m); btree(1,n,1); for(int i = 0; i < m ; i++) { int a,b,v; scanf("%d%d%d",&a,&b,&v); updata(a,b,v,1); } printf("Case %d: The total value of the hook is %d.\n",kase,tree[1].v); } return 0; }