本文主要是介绍TOJ 4399 Deal with numbers / 线段树成段更新，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Deal with numbers
描述
There are n numbers with the corresponding NO.1-n, and the value of the i-th number is xi.
Define three operations:
1.Division a b c, in the interval [a,b], if the value of a number is equal or greater than zero, then its value changed to it divide C(integer division). (1 <= a <= b <= n, 1 <= c <= 50000)
2.Minus a b c, all numbers in the interval [a, b] subtract c. (1 <= a <= b <= n ,1<= c <= 50000)
3.Sum a b, query for the sum of all numbers in the interval [a, b]. (1 <= a <= b <= n)
输入
Input contains several test cases.
The first line is an integer T indicates the number of test cases.
For each test case, the first line contains two integer numbers n and m (1<=n,m<=10^5), indicates the number of numbers and the number of operations. The second line contains n integers, the i-th integer shows the original value of the i-th number (1<=xi<=50000). Then m lines followed, each line shows an operation.
输出
For each set of data, output the case number in a line first, and then for each query, output an integer in a line to show the answer.
Print a blank line after the end of each test cases.
样例输入
2
5 5
1 2 3 4 5
Division 1 3 2
Minus 3 5 3
Sum 1 2
Sum 3 4
Sum 5 5
5 3
-2 -1 3 -2 1
Sum 1 2
Division 1 2 2
Sum 1 2
样例输出
Case 1:
1
-1
2Case 2:
-3
-3 #include <stdio.h>
const __int64 MAX = 100010;
__int64 pos[MAX];
struct node
{__int64 l;__int64 r;__int64 add;__int64 sum;bool b;
}a[MAX*4];void build(__int64 l,__int64 r,__int64 rt)
{a[rt].l = l;a[rt].r = r;a[rt].add = 0;if(l == r){pos[l] = rt;scanf("%I64d",&a[rt].sum);a[rt].b = a[rt].sum > 0;return;}__int64 m = (l + r) >> 1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);a[rt].b = a[rt<<1].b | a[rt<<1|1].b;a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
}void update1(__int64 l,__int64 r,__int64 rt,__int64 divide)
{if(!a[rt].b)return;if(a[rt].l == a[rt].r){if(a[rt].sum > 0)a[rt].sum /= divide;a[rt].b = a[rt].sum > 0;return;}if(a[rt].add){__int64 k = a[rt].r - a[rt].l + 1;a[rt<<1].add += a[rt].add;a[rt<<1|1].add += a[rt].add;a[rt<<1].sum -= a[rt].add * (k - (k >> 1));a[rt<<1|1].sum -= a[rt].add * (k >> 1);a[rt].add = 0;}__int64 m = (a[rt].l + a[rt].r) >> 1;if(l <= m)update1(l,r,rt<<1,divide);if(r > m)update1(l,r,rt<<1|1,divide);a[rt].b = a[rt<<1].b | a[rt<<1|1].b;a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
}void update2(__int64 l,__int64 r,__int64 rt,__int64 add)
{if(a[rt].l == a[rt].r){a[rt].sum -= add;a[rt].b = a[rt].sum > 0;return;}if(a[rt].l >= l && a[rt].r <= r){a[rt].add += add ;a[rt].sum -= add * (a[rt].r - a[rt].l + 1);return;}if(a[rt].add){__int64 k = a[rt].r - a[rt].l + 1;a[rt<<1].add += a[rt].add;a[rt<<1|1].add += a[rt].add;a[rt<<1].sum -= a[rt].add * (k - (k >> 1));a[rt<<1|1].sum -= a[rt].add * (k >> 1);a[rt].add = 0;}__int64 m = (a[rt].l + a[rt].r) >> 1;if(l <= m)update2(l,r,rt<<1,add);if(r > m)update2(l,r,rt<<1|1,add);a[rt].b = a[rt<<1].b | a[rt<<1|1].b;a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
}
__int64 query(__int64 l,__int64 r,__int64 rt)
{if(a[rt].l >= l && a[rt].r <= r){return a[rt].sum;}if(a[rt].add){__int64 k = a[rt].r - a[rt].l + 1;a[rt<<1].add += a[rt].add;a[rt<<1|1].add += a[rt].add;a[rt<<1].sum -= a[rt].add * (k - (k >> 1));a[rt<<1|1].sum -= a[rt].add * (k >> 1);a[rt].add = 0;}__int64 ret = 0;__int64 m = (a[rt].l + a[rt].r) >> 1;if(l <= m)ret += query(l,r,rt<<1);if(r > m)ret += query(l,r,rt<<1|1);return ret;
}
int main()
{char str[100];__int64 t,n,m,x,y,z,i,cas = 1;scanf("%I64d",&t);while(t--){printf("Case %I64d:\n",cas++);scanf("%I64d %I64d",&n,&m);build(1,n,1);while(m--){scanf("%s",str);if(str[0] == 'D'){scanf("%I64d %I64d %I64d",&x,&y,&z);if(z == 1)continue;update1(x,y,1,z);}else if(str[0] == 'M'){scanf("%I64d %I64d %I64d",&x,&y,&z);if(z == 0)continue;update2(x,y,1,z);}else{scanf("%I64d %I64d",&x,&y);printf("%I64d\n",query(x,y,1));}}puts("");}return 0;
}
这篇关于TOJ 4399 Deal with numbers / 线段树成段更新的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
