acm,线段树操作超时,DescriptionYou 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 g
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/29 02:22:27
acm,线段树操作超时,DescriptionYou 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 g
acm,线段树操作超时,
Description
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
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.
Output
You need to answer all Q commands in order.One answer in a line.
Sample Input
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
下面是我的代码
#include
#define MAX 100010
int a[MAX];
struct Tree
{
int left,right,p;
__int64 sum;
} tree[4*MAX];
void build(int id,int l,int r)
{
\x05\x05tree[id].left=l; tree[id].right=r;
\x05\x05tree[id].p=0;
\x05\x05if (l==r)
\x05\x05{
tree[id].sum=a[l];
\x05\x05}
\x05\x05else
\x05\x05{
int mid=(l+r)/2;
\x05\x05\x05build(id*2,l,mid);
\x05\x05\x05build(id*2+1,mid+1,r);
\x05\x05\x05tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
\x05\x05}
}
void update(int id,int l,int r,int val)
{
\x05\x05if (l
acm,线段树操作超时,DescriptionYou 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 g
把询问和的函数那个第一个if里面改成l