HDU - 1698 线段树区间修改，区间查询
这就是很简单的基本的线段树的基本操作，区间修改，区间查询，对区间内部信息打上laze标记，然后维护即可。
我自己做的时候太***了。。。把区间修改写错了，对给定区间进行修改的时候，mid取的是节点的左右的中间值，而不是更新区间的中间值（太菜了）。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxx = 4e5+6; struct node{ int l,r,val,add; }tree[maxx]; inline L(int r){return r<<1;}; inline R(int r){return r<<1|1;}; inline MID(int l,int r){return (l+r)>>1;}; void pushdown(int root){ if (tree[root].add){ tree[L(root)].add=tree[root].add; tree[R(root)].add=tree[root].add; tree[L(root)].val=(tree[L(root)].r-tree[L(root)].l+1)*tree[root].add; tree[R(root)].val=(tree[R(root)].r-tree[R(root)].l+1)*tree[root].add; tree[root].add=0; } } void buildtree(int root,int l,int r){ tree[root].l=l; tree[root].r=r; tree[root].add=0; tree[root].val=0; if (l==r){ tree[root].val=1; return; } int mid=MID(l,r); buildtree(L(root),l,mid); buildtree(R(root),mid+1,r); tree[root].val=tree[L(root)].val+tree[R(root)].val; } void update(int root,int ul,int ur,int c){ int l = tree[root].l,r=tree[root].r; if (ul<=l && r<=ur){ tree[root].val=(r-l+1)*c; tree[root].add=c; return; } int mid=MID(l,r);//这里一定要注意是取root左右界的中点 if (ul<=mid) { pushdown(root); update(L(root),ul,ur,c); } if (ur>mid) { pushdown(root); update(R(root),ul,ur,c); } tree[root].val=tree[L(root)].val+tree[R(root)].val; } int main(){ int t,n,cas=0,q; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); memset(tree,0,sizeof(tree)); buildtree(1,1,n); int x,y,z; while(q--){ scanf("%d%d%d",&x,&y,&z); update(1,x,y,z); } printf("Case %d: The total value of the hook is %d.\n",++cas,tree[1].val); } return 0; }
投递旷视等公司10个岗位 >
拼多多集团-PDD工作强度 286人发布