继续刷线段树的简单题
有线段树的更新
#include<iostream> using namespace std; #define N 100005 struct node { int l,r,bj,z; }; node st[N*4]; void build(int l,int r,int i) { st[i].l=l,st[i].r=r; st[i].bj=1,st[i].z=1; if(l==r) return ; int mid=(l+r)/2; build(l,mid,2*i); build(mid+1,r,2*i+1); return ; } void update(int l,int r,int z,int i) { if(st[i].l>=l&&st[i].r<=r) { st[i].bj=1,st[i].z=z; return ; } if(st[i].bj) { st[2*i].bj=st[2*i+1].bj=1; st[2*i].z=st[2*i+1].z=st[i].z; st[i].bj=0; } int mid=(st[i].l+st[i].r)/2; if(l>mid) update(l,r,z,2*i+1); else if(r<=mid) update(l,r,z,2*i); else { update(l,mid,z,2*i); update(mid+1,r,z,2*i+1); } return ; } int query(int i) { if(st[i].bj) return (st[i].r-st[i].l+1)*st[i].z; else return query(2*i)+query(2*i+1); } int main() { int ca,n,x,y,z,i,j,m; scanf("%d",&ca); for(i=1;i<=ca;i++) { scanf("%d%d",&n,&m); build(1,n,1); for(j=1;j<=m;j++) { scanf("%d%d%d",&x,&y,&z); update(x,y,z,1); } printf("Case %d: The total value of the hook is %d./n",i,query(1)); } return 0; }
