poj3468 Simple Problem with Integers (线段树)
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input <dl><dd>The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
You need to answer all Q commands in order. One answer in a line.
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4</dd> Sample Output <dd>
4 55 9 15</dd> Hint <dd>
The sums may exceed the range of 32-bit integers.
//by swust_t_p
</dd></dl>#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
struct node
{
long long int num;
long long int left, right,mark;
};
node shu[2000000];
void creatshu(long long int l,long long int r,int i)
{
shu[i].left = l;
shu[i].right = r;
shu[i].mark = 0;
shu[i].num = 0;
if (l==r)
{
scanf("%lld", &shu[i].num);
return;
}
long long int mid = (l + r) / 2;
creatshu(l, mid, i * 2);
creatshu(mid + 1, r, i * 2 + 1);
shu[i].num = shu[i * 2].num + shu[i * 2 + 1].num;
return;
}
void pushnext(long long mark, int i)
{
shu[i].mark += mark;
shu[i].num += (shu[i].right - shu[i].left + 1)*mark;
}
void add(long long int l,long long int r, long long int mark, int i)
{
if (shu[i].left == l && shu[i].right == r)
{
shu[i].num += (shu[i].right - shu[i].left + 1)*mark;
shu[i].mark += mark;
}
else
{
long long int mid = (shu[i].left + shu[i].right) / 2;
/*if (shu[i].mark != 0)
{
add(shu[i].left, mid, shu[i].mark, i * 2);
add(mid+1, shu[i].right, shu[i].mark, i * 2 + 1);
shu[i].mark = 0;
}*/
if (shu[i].mark != 0)
{
pushnext(shu[i].mark, i * 2);
pushnext(shu[i].mark, i * 2 + 1);
shu[i].mark = 0;
}
shu[i].num += (r - l + 1)*mark;
if (r <= mid)
{
add(l,r, mark, i * 2);
}
else if (l > mid)
{
add(l,r, mark, i * 2 + 1);
}
else if (l <= mid && r > mid)
{
add(l, mid, mark, i * 2);
add(mid + 1, r, mark, i * 2 + 1);
}
}
}
long long int search(long long int l,long long int r,int i)
{
if (shu[i].left == l && shu[i].right == r)
{
return shu[i].num;
}
else
{
long long int mid = (shu[i].left + shu[i].right) / 2;
/*f (shu[i].mark!=0)
{
if (r <= mid)
{
add(l, r, shu[i].mark, i * 2);
}
else if (l > mid)
{
add(l, r, shu[i].mark, i * 2 + 1);
}
else if (l <= mid && r > mid)
{
add(l, mid, shu[i].mark, i * 2);
add(mid + 1, r, shu[i].mark, i * 2 + 1);
}
shu[i].mark = 0;
}*/
if (shu[i].mark != 0)
{
pushnext(shu[i].mark, i * 2);
pushnext(shu[i].mark, i * 2 + 1);
shu[i].mark = 0;
}
if (r <= mid)
{
return search(l, r, i * 2);
}
else if (l > mid)
{
return search(l, r, i * 2 + 1);
}
else if (l <= mid && r > mid)
{
return search(l, mid, i * 2)+search(mid+1,r,i*2+1);
}
}
}
int main()
{
long long int len, ordernum;
while (~scanf("%lld %lld", &len, &ordernum))
{
creatshu(1, len, 1);
char order[100];
long long int left, right,mark;
for (int i = 0; i < ordernum; i++)
{
scanf("%s", order);
if (order[0] == 'Q')
{
scanf("%lld %lld", &left, &right);
printf("%lld\n", search(left, right, 1));
}
else if (order[0] == 'C')
{
scanf("%lld %lld %lld", &left, &right, &mark);
add(left, right, mark, 1);
}
}
}
return 0;
}//by swust_t_p
投递腾讯等公司10个岗位 >
