点击打开链接
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int M=1e5+20; long long sum[M*4],lazy[M*4];//lazy标记 struct node{ int l,r; int mid() { return (l+r)>>1; } }seg[M<<2]; void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { seg[rt].l=l; seg[rt].r=r; lazy[rt]=0; if(l==r) { sum[rt]=1;//初始化 return; } int m=seg[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt); } void Pushdown(int rt,int l) { if(lazy[rt]) { lazy[rt<<1]=lazy[rt];//传递lazy标记 lazy[rt<<1|1]=lazy[rt]; sum[rt<<1]=lazy[rt]*(l-l/2); sum[rt<<1|1]=lazy[rt]*(l/2); lazy[rt]=0;//更新后取消lazy标记 } } void update(int c,int l,int r,int rt) { if(seg[rt].l==l&&seg[rt].r==r) { sum[rt]=c*(r-l+1);// //把(l,r)中的元素都替换成c lazy[rt]=c;//先不更新子节点 lazy标记 return; } //要分解区间时 把以前没更新的先更新 Pushdown(rt,seg[rt].r-seg[rt].l+1); int m=seg[rt].mid(); //要更新的在节点左边 if(r<=m) { update(c,l,r,rt<<1); } else if(l>m) { update(c,l,r,rt<<1|1); } else//要更新的横跨中点 { update(c,l,m,rt<<1); update(c,m+1,r,rt<<1|1); } pushup(rt); } long long query(int l,int r,int rt) { if(l==seg[rt].l&&r==seg[rt].r)//完全包含 { return sum[rt]; } //要用到子区间 Pushdown(rt,seg[rt].r-seg[rt].l+1); int m=seg[rt].mid(); long long res=0; //分解区间 if(r<=m) { res+=query(l,r,rt<<1); } else if(l>m)//所查询区间在右半段 { res+=query(l,r,rt<<1|1); } else//l<m<r<tree[rt].r { res+=query(l,m,rt<<1); res+=query(m+1,r,rt<<1|1); } return res; } int main() { int t; cin>>t; for(int i=1;i<=t;i++) { int n; cin>>n; build(1,n,1); int q; cin>>q; while(q--) { int l,r,val; scanf("%d%d%d",&l,&r,&val); update(val,l,r,1); } printf("Case %d: The total value of the hook is %lld.\n",i,query(1,n,1)); } return 0; }