线段树区间更新hdu1698

第一种是sum存放每个点的值，然后区间更新，把需要更新的父亲的sum设为-1，，代表此区间有被更新过，就不由挪动子节点了。

vj上跑的时间这个快一点。

另一种lazy标志位，区间更新时，把lazy标志位设为1，当查找的区间含lazy过的，就变更子节点位原来的值，所以需要一个tag记录原来的值。

</pre><pre name="code" class="cpp">#include<bits/stdc++.h>using namespace std;#define N 100100struct {int sum;int left,right;}b[N*4];void build(int left,int right,int i){int mid;b[i].left=left;b[i].right=right;b[i].sum=1;if(left==right) {b[i].sum=1;return ;}mid = (left+right)/2;build(left,mid,2*i);build(mid+1,right,2*i+1);}void Qujian(int x,int y,int i,int num){if(b[i].sum==num) return ;if(b[i].left ==x&&y== b[i].right){ b[i].sum=num;return ; }if(b[i].sum!=-1){b[2*i].sum=b[2*i+1].sum=b[i].sum;b[i].sum=-1;}int mid = (b[i].left+b[i].right)>>1;if(x>mid) Qujian(x,y,2*i+1,num);else if(y<=mid) Qujian(x,y,2*i,num);else { Qujian(mid+1,y,2*i+1,num); Qujian(x,mid,2*i,num); }}int sum_(int i){if(b[i].sum!=-1){ return (b[i].right-b[i].left+1)*b[i].sum; }else return sum_(2*i+1)+sum_(2*i);}int main(){int t,kase=1;scanf("%d",&t);while(t–){memset(b,0,sizeof(b));int n,m;scanf("%d%d",&n,&m);build(1,n,1);while(m–){int x,y,z;scanf("%d%d%d",&x,&y,&z);Qujian(x,y,1,z);}printf("Case %d: The total value of the hook is %d.\n",kase++,sum_(1));}}#include<bits/stdc++.h>using namespace std;#define N 100100struct {int sum;int left,right;int lazy,tag;}b[N*4];void build(int left,int right,int i){int mid;b[i].left=left;b[i].right=right;b[i].sum=1;b[i].lazy=0;b[i].tag=0;if(left==right) {b[i].sum=1;return ;}mid = (left+right)/2;build(left,mid,2*i);build(mid+1,right,2*i+1);}void Updata(int x,int y,int i,int num){if(b[i].left ==x&&y== b[i].right){ b[i].sum=num*(b[i].right-b[i].left+1); b[i].lazy = 1; b[i].tag=num; return ; }int mid = (b[i].left+b[i].right)>>1;if(b[i].lazy==1){b[i].lazy=0;Updata(b[i].left,mid,i*2,b[i].tag);Updata(mid+1,b[i].right,i*2+1,b[i].tag);}if(x>mid) Updata(x,y,2*i+1,num);else if(y<=mid) Updata(x,y,2*i,num);else { Updata(mid+1,y,2*i+1,num); Updata(x,mid,2*i,num); }b[i].sum = b[i*2].sum + b[i*2+1].sum;}int main(){int t,kase=1;scanf("%d",&t);while(t–){memset(b,0,sizeof(b));int n,m;scanf("%d%d",&n,&m);build(1,n,1);while(m–){int x,y,z;scanf("%d%d%d",&x,&y,&z);Updata(x,y,1,z);}printf("Case %d: The total value of the hook is %d.\n",kase++,b[1].sum);}}

一直觉得人应该去旅行，在年轻的时候，趁着有脾气装潇洒，

相关文章：

你感兴趣的文章：

标签云：