P3372 【模板】线段树 1

admin

题目描述
如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：
输出包含若干行整数，即为所有操作2的结果。

输入输出样例
输入样例#1：
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例#1：
11
8
20
说明
时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^，保证在int64/long long数据范围内）

样例说明：

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. const int N = 2e5 + 10;
    
14. typedef long long LL;
    
15. LL sum[N * 4]= {0}, tag[N * 4]= {0},a[N];
    
16. void build(int l, int r, int o)
    
17. {
    
18.         if(l == r)
    
19.         {
    
20.                 sum[o] = a[l];
    
21.                 tag[o] = 0;
    
22.                 return ;
    
23.         }
    
24.         int mid = (l + r) >> 1;
    
25.         build(l, mid, o * 2);
    
26.         build(mid + 1, r, o << 1 | 1);
    
27.         sum[o] = sum[o << 1] + sum[o << 1 | 1];
    
28.         tag[o] = 0;
    
29.         return ;
    
30. }
    
31. void update(int L, int R, LL add, int l, int r, int o)
    
32. {
    
33.         if(L <= l && r <= R)
    
34.         {
    
35.                 sum[o] += (r - l + 1) * add;
    
36.                 tag[o] += add;
    
37.                 return ;
    
38.         }
    
39.         int mid = (l + r) >> 1;
    
40.         if(tag[o])
    
41.         {
    
42.                 sum[o << 1] += tag[o] * (mid - l + 1);
    
43.                 tag[o << 1] += tag[o];
    
44.                 sum[o << 1|1] += tag[o] * (r - mid);
    
45.                 tag[o << 1|1] += tag[o];
    
46.                 tag[o] = 0;
    
47.         }
    
48.         if(L <= mid) update(L, R, add, l, mid, o << 1);
    
49.         if(R > mid) update(L, R, add, mid + 1, r, o << 1 | 1);
    
50.         sum[o] = sum[o << 1] + sum[o << 1 | 1];
    
51. }
    
52. LL query(int L, int R, int l, int r, int o)
    
53. {
    
54.         if(L <= l && r <= R)
    
55.         {
    
56.                 return sum[o];
    
57.         }
    
58.         int mid = (l + r) >> 1;
    
59.         if(tag[o])
    
60.         {
    
61.                 sum[o << 1] += tag[o] * (mid - l + 1);
    
62.                 tag[o << 1] += tag[o];
    
63.                 sum[o << 1|1] += tag[o] * (r - mid);
    
64.                 tag[o << 1|1] += tag[o];
    
65.                 tag[o] = 0;
    
66.         }
    
67.         LL ans = 0;
    
68.         if(L <= mid) ans += query(L, R, l, mid, o << 1);
    
69.         if(R > mid) ans += query(L, R, mid + 1, r, o << 1 | 1);
    
70.         return ans;
    
71. }
    
72. 
    
73. int main()
    
74. {
    
75.         int n, m;
    
76.         scanf("%d %d", &n, &m);
    
77.         for(int i=1; i<=n; i++)
    
78.                 scanf("%lld", &a[i]);
    
79.         build(1, n, 1);
    
80.         while(m --)
    
81.         {
    
82.                 int op;
    
83.                 scanf("%d", &op);
    
84.                 if(op == 1)
    
85.                 {
    
86.                         int l, r;
    
87.                         LL x;
    
88.                         scanf("%d %d %lld", &l, &r, &x);
    
89.                         update(l, r, x, 1, n, 1);
    
90.                 }
    
91.                 else
    
92.                 {
    
93.                         int l, r;
    
94.                         scanf("%d %d", &l, &r);
    
95.                         printf("%lld\n", query(l, r, 1, n, 1));
    
96.                 }
    
97.         }
    
98. }

复制代码

admin

zmq同学好厉害呀！

倚窗倾听风吹雨

1. #include<iostream>
   
2. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
3. using namespace std;
   
4. typedef long long int ll;
   
5. const int N=100005;
   
6. int L,R,m,n;
   
7. ll a[N],sum[N<<2],add[N<<2],ans,ad,k;
   
8. inline void PushUp(int l,int r,int p){sum[p]=sum[p<<1]+sum[(p<<1)|1]+add[p]*(r-l+1);}
   
9. void BuildTree(int l,int r,int p)
   
10. {
    
11.     if(l==r){sum[p]=a[l];return;}
    
12.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
13.     BuildTree(l,mid,ls);
    
14.     BuildTree(mid+1,r,rs);
    
15.     PushUp(l,r,p);return;
    
16. }
    
17. void Add(int l,int r,int p)
    
18. {
    
19.     if(L<=l && r<=R){sum[p]+=k*(r-l+1);add[p]+=k;return;}
    
20.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
21.     if(L<=mid) Add(l,mid,ls);
    
22.     if(R>mid) Add(mid+1,r,rs);
    
23.     PushUp(l,r,p);return;
    
24. }
    
25. void query(int l,int r,int p)
    
26. {
    
27.     if(L<=l && r<=R){ans+=sum[p]+ad*(r-l+1);return;}
    
28.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
29.     ad+=add[p];
    
30.     if(L<=mid)query(l,mid,ls);
    
31.     if(R>mid)query(mid+1,r,rs);
    
32.     ad-=add[p];return;
    
33. }
    
34. void print(int l,int r,int p)
    
35. {
    
36.     cout<<l<<" "<<r<<" "<<p<<" "<<sum[p]<<" "<<add[p]<<endl;
    
37.     if(l==r)return;
    
38.     int mid=l+((r-l)>>1),ls=p<<1,rs=p<<1|1;
    
39.     print(l,mid,ls);
    
40.     print(mid+1,r,rs);
    
41. }
    
42. int main()
    
43. {
    
44.     cin>>n>>m;
    
45.     FOR(i,1,n)cin>>a[i];
    
46.     BuildTree(1,n,1);
    
47.     while(m--)
    
48.     {
    
49.         int x;
    
50.         cin>>x>>L>>R;
    
51.         if(x==1)
    
52.         {
    
53.             cin>>k;
    
54.             Add(1,n,1);
    
55.          ///   print(1,n,1);
    
56.          ///   cout<<"---------------"<<endl;
    
57.         }
    
58.         else
    
59.         {
    
60.             ans=0;ad=0;
    
61.             query(1,n,1);
    
62.             cout<<ans<<endl;
    
63.         }
    
64.     }
    
65.     return 0;
    
66. }
    

复制代码

admin

基本线段树