首页 > 代码库 > HDU 1698
HDU 1698
线段树,懒惰标记
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 #define N 400010 5 int sum[N],lazy[N]; 6 void pushup(int root){ 7 sum[root]=sum[root*2]+sum[root*2+1]; 8 } 9 void pushdown(int root,int x){10 if(lazy[root] != -1) {11 lazy[root*2] = lazy[root*2+1] = lazy[root];12 sum[root*2]=(x-x/2)*lazy[root];13 sum[root*2+1]=x/2*lazy[root];14 lazy[root]=-1;15 }16 }17 void build(int l,int r,int root){18 lazy[root]=-1,sum[root]=1;19 if(l==r)return ;20 int mid=(l+r)/2;21 build(l,mid,root*2);22 build(mid+1,r,root*2+1);23 pushup(root);24 }25 26 void query(int x,int y,int l,int r,int root,int a){27 if(x<=l&&y>=r){28 lazy[root] = a;29 sum[root] = a*(r-l+1);30 return;31 }32 pushdown(root,r-l+1);33 int mid=(r+l)/2;34 if(x<=mid)query(x,y,l,mid,root*2,a);35 if(y>mid)query(x,y,mid+1,r,root*2+1,a);36 pushup(root);37 }38 int main(){39 //freopen("test.txt","r",stdin);40 int t,n,q,x,y,z,case1=0;41 scanf("%d",&t);42 while(t--){43 case1++;44 scanf("%d%d",&n,&q);45 build(1,n,1);46 for(int i=0;i<q;i++){47 scanf("%d%d%d",&x,&y,&z);48 query(x,y,1,n,1,z);49 }50 printf("Case %d: The total value of the hook is %d.\n",case1,sum[1]);51 }52 return 0;53 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。