Tree Recovery

链接：https://www.nowcoder.com/acm/contest/77/H
来源：牛客网

Tree Recovery

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

You have N integers, A₁, A₂, ... , A_N. 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.

输入描述:

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

输出

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 #define lson rt<<1  
 4 #define rson rt<<1|1  
 5 #define ll long long  
 6 const int maxn=1e5+7;  
 7 ll a[maxn],add[maxn<<2];  
 8 struct node  
 9 {  
10     int left,right,mid;  
11     ll sum;  
12 }c[maxn<<2];  
13 void build(int l,int r,int rt)  
14 {  
15     add[rt]=0;  
16     c[rt].left=l;  
17     c[rt].right=r;  
18     c[rt].mid=(l+r)>>1;  
19     if(l==r)  
20     {  
21         c[rt].sum=a[l];  
22         return;  
23     }  
24     build(l,c[rt].mid,lson);  
25     build(c[rt].mid+1,r,rson);  
26     c[rt].sum=c[lson].sum+c[rson].sum;  
27 }  
28 void Push_down(int rt)  
29 {  
30     if(add[rt]!=0)  
31     {  
32         add[lson]+=add[rt];  
33         add[rson]+=add[rt];  
34         //这里注意，add[lson],add[rson]此时不一定已经更新了，  
35         //因此是在原来的基础上加，不是直接赋值  
36         c[lson].sum+=(c[lson].right-c[lson].left+1)*add[rt];  
37         c[rson].sum+=(c[rson].right-c[rson].left+1)*add[rt];  
38         add[rt]=0;  
39     }  
40 }  
41 void update(int l,int r,ll C,int rt)  
42 {  
43     if(l<=c[rt].left&&r>=c[rt].right)  
44     {  
45         add[rt]+=C;  
46         c[rt].sum+=(c[rt].right-c[rt].left+1)*C;  
47         return;  
48     }  
49     Push_down(rt);  
50     if(l<=c[rt].mid)update(l,r,C,lson);  
51     if(r>c[rt].mid)update(l,r,C,rson);  
52     c[rt].sum=c[lson].sum+c[rson].sum;  
53 }  
54 ll query(int l,int r,int rt)  
55 {  
56     if(l<=c[rt].left&&r>=c[rt].right)  
57         {  
58             return c[rt].sum;  
59         }  
60     Push_down(rt);  
61     int m=(c[rt].left+c[rt].right)>>1;  
62     ll ans=0;  
63     if(l<=m)ans+=query(l,r,lson);  
64     if(r>m) ans+=query(l,r,rson);  
65     return ans;  
66 }  
67 int main()  
68 {  
69     ll n,Q,i,j;  
70     scanf("%lld%lld",&n,&Q);  
71     for(i=1;i<=n;i++)  
72         scanf("%lld",&a[i]);  
73     build(1,n,1);  
74     while(Q--)  
75     {  
76         char t[5];int x,y;  
77         scanf("%s%d%d",&t,&x,&y);  
78         if(t[0]=='C')  
79         {  
80             ll z;scanf("%lld",&z);  
81             update(x,y,z,1);  
82         }  
83         else  
84         {  
85              printf("%lld
",query(x,y,1));  
86         }  
87     }  
88     return 0;  
89 }

View Code

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n,m,x,y,sum,i,z,a[100002];
 5     char f;
 6     scanf("%d%d",&n,&m);
 7     for(i=1;i<=n;i++)
 8         scanf("%d",&a[i]);
 9         getchar();
10         while(m--)
11     {
12         sum=0;
13         scanf("%c",&f);
14   
15     if(f=='C')
16     {scanf("%d%d%d",&x,&y,&z);
17         for(i=x;i<=y;i++)
18             a[i]+=z;
19     }
20     if(f=='Q')
21     {
22         scanf("%d%d",&x,&y);
23         for(i=x;i<=y;i++)
24             sum+=a[i];
25         printf("%d
",sum);
26     }
27     getchar();
28     }
29     return 0;
30 }