TOJ 4399 Deal with numbers / 线段树成段更新
Deal with numbers时间限制(普通/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
#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;
}
补充：软件开发 , C++ ,
