http://acm.hdu.edu.cn/showproblem.php?pid=1698
这个题意翻译起来有点猥琐啊,还是和谐一点吧
和涂颜色差不多,区间初始都为1,然后操作都是将x到y改为z,注意 是改为z,不是加或减,最后输出区间总值
也是线段树加lazy操作
1 #include<cstdio> 2 using namespace std; 3 struct point { 4 int l,r; 5 int val,sum; 6 }; 7 point tree[400007]; 8 void build(int i,int left,int right) 9 { 10 tree[i].l=left,tree[i].r=right; 11 tree[i].val=0; 12 if (left==right) {tree[i].sum=1;return;} 13 int mid=(left+right)/2; 14 build(i*2,left,mid); 15 build(i*2+1,mid+1,right); 16 tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; 17 } 18 int update(int i,int left,int right,int val) 19 { 20 if (right==tree[i].r&&left==tree[i].l) 21 { 22 tree[i].val=val; 23 return tree[i].sum=(right-left+1)*val; 24 } 25 if (tree[i].val) 26 { 27 tree[i*2].val=tree[i*2+1].val=tree[i].val; 28 tree[i*2].sum=(tree[i*2].r-tree[i*2].l+1)*tree[i].val; 29 tree[i*2+1].sum=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].val; 30 tree[i].val=0; 31 } 32 int mid=(tree[i].r+tree[i].l)/2; 33 if (left>mid) return tree[i].sum=update(i*2+1,left,right,val)+tree[i*2].sum; 34 else if (right<=mid) return tree[i].sum=update(i*2,left,right,val)+tree[i*2+1].sum; 35 else return tree[i].sum=update(i*2+1,mid+1,right,val)+update(i*2,left,mid,val); 36 } 37 int main() 38 { 39 int t,n,m,x,y,z,sum; 40 while (~scanf("%d",&t)) 41 { 42 sum=1; 43 while (t--) 44 { 45 scanf("%d %d",&n,&m); 46 build(1,1,n); 47 while (m--) 48 { 49 scanf("%d %d %d",&x,&y,&z); 50 update(1,x,y,z); 51 } 52 printf("Case %d: The total value of the hook is %d. ",sum++,tree[1].sum); 53 } 54 } 55 return 0; 56 }
http://poj.org/problem?id=3468
这个和上面一样,只是变成了加上z,所以就变成了在原有的值上再加,+=，改改就行,数值比较大,应该用int64
1 #include<cstdio> 2 #define ll __int64 3 using namespace std; 4 struct point { 5 ll l,r; 6 ll val,sum; 7 }; 8 point tree[400007]; 9 ll num[100007]; 10 void build(ll i,ll left,ll right) 11 { 12 tree[i].l=left,tree[i].r=right; 13 tree[i].val=0; 14 if (left==right) {tree[i].sum=num[left];return;} 15 int mid=(left+right)/2; 16 build(i*2,left,mid); 17 build(i*2+1,mid+1,right); 18 tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; 19 } 20 ll update(ll i,ll left,ll right,ll val) 21 { 22 if (right==tree[i].r&&left==tree[i].l) 23 { 24 tree[i].val+=val; 25 return tree[i].sum+=(right-left+1)*val; 26 } 27 if (tree[i].val) 28 { 29 tree[i*2].val+=tree[i].val; 30 tree[i*2+1].val+=tree[i].val; 31 tree[i*2].sum+=(tree[i*2].r-tree[i*2].l+1)*tree[i].val; 32 tree[i*2+1].sum+=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].val; 33 tree[i].val=0; 34 } 35 int mid=(tree[i].r+tree[i].l)/2; 36 if (left>mid) return tree[i].sum=update(i*2+1,left,right,val)+tree[i*2].sum; 37 else if (right<=mid) return tree[i].sum=update(i*2,left,right,val)+tree[i*2+1].sum; 38 else return tree[i].sum=update(i*2+1,mid+1,right,val)+update(i*2,left,mid,val); 39 } 40 ll find(ll i,ll left,ll right) 41 { 42 if (left>tree[i].r&&right<tree[i].l) return 0; 43 if (tree[i].l==left&&tree[i].r==right) return tree[i].sum; 44 if (tree[i].val) 45 { 46 tree[i*2].val+=tree[i].val; 47 tree[i*2+1].val+=tree[i].val; 48 tree[i*2].sum+=(tree[i*2].r-tree[i*2].l+1)*tree[i].val; 49 tree[i*2+1].sum+=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].val; 50 tree[i].val=0; 51 } 52 ll mid=(tree[i].r+tree[i].l)/2; 53 if (left>mid) return find(i*2+1,left,right); 54 else if (right<=mid) return find(i*2,left,right); 55 else return find(i*2,left,mid)+find(i*2+1,mid+1,right); 56 } 57 int main() 58 { 59 ll n,m,i,z,x,y; 60 char op; 61 while (~scanf("%I64d %I64d",&n,&m)) 62 { 63 for (i=1;i<=n;i++) 64 scanf("%I64d",&num[i]); 65 build(1,1,n); 66 while (m--) 67 { 68 scanf(" %c",&op); 69 if (op=='C') 70 { 71 scanf("%I64d %I64d %I64d",&x,&y,&z); 72 update(1,x,y,z); 73 } 74 else 75 { 76 scanf("%I64d %I64d",&x,&y); 77 printf("%I64d ",find(1,x,y)); 78 } 79 } 80 } 81 return 0; 82 }