这两题我都在之前做过，但并未通过，那次做的时候是刚开始接触线段树，现在有了一点点的了解，翻出以前的代码稍作修改就AC了。之前1698错误的原因是没有注意到位运算的优先级。
//hdoj 1698 #include<stdio.h> #include<string.h> #define maxn 100010 struct node { int l; int r; int mid; int val; }tree[maxn<<2]; void buildtree(int o,int l,int r) { tree[o].val = 1; tree[o].l = l; tree[o].r = r; tree[o].mid = (l + r)>>1; if(l == r) return ; else { buildtree(o<<1, l, tree[o].mid); buildtree((o<<1)+1, tree[o].mid + 1, r); } } void update(int o, int l, int r, int val) { if(l == tree[o].l && r == tree[o].r) { tree[o].val = val; return ; } //递归边界，如果更新的边界和节点边界相同则返回 if(tree[o].val != 0) { tree[o<<1].val = tree[o].val; tree[(o<<1)+1].val = tree[o].val; tree[o].val = 0; } //这个地方是为了表示tree[o]的两个节点的val值是不一样的 //要更新的段无非三种情况，要么在l-mid段，要么在mid-r段，再么就是两端都存在的，分情况递归 if(r <= tree[o].mid) update(o<<1, l, r, val); //这个是位于l-mid段的 else if(l > tree[o].mid) update((o<<1)+1, l, r, val); //这个是位于mid-r段的 else { update(o<<1, l, tree[o].mid, val); update((o<<1)+1, tree[o].mid + 1, r, val); } //两段都有的情况 } int getsum(int o,int l,int r) { if(tree[o].val > 0) return tree[o].val * (tree[o].r - tree[o].l + 1); //tree[o].val > 0 证明在tree[o].l到tree[o].r区间里面的val都是一样的，要获取的区间也属于该区间 if(r <= tree[o].mid) return getsum(o * 2, l, r); //同 update（） 也是分三种情况 else if (l > tree[o].mid) return getsum((o<<1)+1, l, r); else return getsum(o<<1, l, tree[o].mid) + getsum((o<<1)+1, tree[o].mid, r); } int main() { int t, n, i, j, op, x, y, z; scanf("%d",&t); for(i = 1;i <= t;i++) { scanf("%d",&n); buildtree(1, 1, n); scanf("%d",&op); while(op--) { scanf("%d%d%d",&x,&y,&z); update(1, x, y, z); } int ans = getsum(1,1,n); printf("Case %d: The total value of the hook is %d.\n",i,ans); } return 0; }
//hdoj 1754 #include<stdio.h> #include<string.h> #define maxn 200005 struct node { int l; int r; int mid; int max; }tree[maxn<<2]; int arr[maxn]; int max(int a,int b) { return a > b ? a : b; } void build(int o, int l, int r) { tree[o].l = l; tree[o].r = r; tree[o].mid = (l + r)>>1; if(l == r) { tree[o].max = arr[l]; return ; } build(o<<1, l, tree[o].mid); build((o<<1)+1, tree[o].mid + 1, r); tree[o].max = max(tree[o<<1].max, tree[(o<<1)+1].max); } void update(int o, int l, int r,int a, int val) { tree[o].max = max(tree[o].max, val); if(tree[o].l == tree[o].r) { return ; } if(a <= tree[o].mid) update(o<<1,l,tree[o].mid,a,val); else update((o<<1)+1, tree[o].mid + 1, r, a, val); } int query(int o,int l,int r) { if(l == tree[o].l && r == tree[o].r) return tree[o].max; if(r <= tree[o].mid) return query(o*2,l,r); if(l > tree[o].mid) return query((o<<1)+1, l, r); return max(query(o<<1, l, tree[o].mid),query((o<<1)+1, tree[o].mid+1, r)); } int main() { int n, m, i, t, a, b; char c; while(scanf("%d%d",&n,&m) != EOF) { for(i = 1;i <= n;i++) { scanf("%d",&arr[i]); } build(1,1,n); while(m--) { getchar(); scanf("%c%d%d",&c,&a,&b); if(c == 'U') update(1,1,n,a,b); else printf("%d\n",query(1,a,b)); } } return 0; }
