早教吧作业答案频道 -->其他-->
acm,线段树操作超时,DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinag
题目详情
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
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
▼优质解答
答案和解析
把询问和的函数那个第一个if里面改成l
看了 acm,线段树操作超时,De...的网友还看了以下:
图(1)中,C点为线段AB上一点,△ACM,△CBN是等边三角形,AN与BM相等吗?说明理由;如图 2020-04-07 …
sql字段an内容3,184,205表user里有一字段an内容为3,184,205,304,55 2020-04-07 …
matlab中数组作图---线段(颜色交替)一堆离散的数据,能否把它合成一条,不同颜色的线段?根据 2020-05-16 …
已知B是线段AC上的一点,M是线段AB的中点,N是线段AC的中点,P为NA的中点,Q为MA的中点, 2020-05-16 …
已知:点C为线段AB上一点,△ACM、△CBN是等边三角形,已知:点C为线段AB上一点,△ACM、 2020-06-06 …
acm,线段树操作超时,DescriptionYouhaveNintegers,A1,A2,... 2020-06-13 …
斐波那契数列{an}满足:a1=1,a2=1,an=an-1+an-2(n≥3,n∈N*).若将数 2020-07-23 …
画线段MN=3cm,在线段MN上取一点Q,使MQ=NQ,延长线段MN至点A,使AN=12MN;延长 2020-07-25 …
数列{an}满足an+1=(分段函数,且n+1为下标)an大于等于t时:an-tan小于t时:t+ 2020-07-29 …
若存在常数k(k∈N*,k≥2)、d、t(d,t∈R),使得无穷数列{an}满足an+1=an+d 2020-08-02 …