时间限制(普通/
Java):10000MS/30000MS 运行内存限制:65536KByte
描述
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
2
Case 2:
-3
-3
#includeconst __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; }