华师一附中OI组

标题: P3372 【模板】线段树 1 [打印本页]
作者: admin    时间: 2018-5-13 01:09
标题: P3372 【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：

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数据范围内）

样例说明：

作者: 吴语林    时间: 2018-7-29 19:35
  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. }

  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. }
复制代码
作者: ZMQ    时间: 2018-8-16 21:57
提示: 作者被禁止或删除 内容自动屏蔽
作者: admin    时间: 2018-8-17 08:50
zmq同学好厉害呀！
作者: 倚窗倾听风吹雨    时间: 2018-10-4 13:47
  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    时间: 2020-5-4 12:46
基本线段树



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2