华师一附中OI组

标题: P3372 【模板】线段树1 [打印本页]
作者: liubo    时间: 2018-7-29 19:03
标题: 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：[url=]复制[/url]5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
输出样例#1：[url=]复制[/url]11820

说明时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：



作者: liubo    时间: 2018-7-29 19:04
  1. #include<iostream>
  2. using namespace std;
  3. struct node{
  4.     int l,r;
  5.     long long sum;
  6.     long long inc;
  7.     int mid(){
  8.         return (l + r)/2;
  9.     }
  10. }t[300010];
  11. void buildTree(int root,int l,int r){
  12.     node &n = t[root];
  13.     n.l = l;
  14.     n.r = r;
  15.     n.sum = 0;
  16.     n.inc = 0;
  17.     /**!!!**/if(l == r) return;
  18.     buildTree(root * 2 + 1,l,n.mid());
  19.     buildTree(root * 2 + 2,n.mid() + 1,r);
  20. }
  21. void insertNum(int root,int i,int v){
  22.     node &n = t[root];
  23.     if(n.l == n.r && n.l == i){
  24.         n.sum = v;
  25.         return;
  26.     }
  27.     n.sum += v;
  28.     if(i > n.mid())
  29.         insertNum(root * 2 + 2,i,v);
  30.     else
  31.         insertNum(root * 2 + 1,i,v);
  32. }
  33. void addNum(int root,int l,int r,int v){
  34.     node &n = t[root];
  35.     if(n.l == l && n.r == r){
  36.         n.inc += v;
  37.         return;
  38.     }
  39.     //n.inc += v;
  40.     n.sum += v * (r - l + 1);
  41.     if(l > n.mid())
  42.         addNum(root * 2 + 2,l,r,v);
  43.     else if(r <= n.mid())
  44.         addNum(root * 2 + 1,l,r,v);
  45.     else{
  46.         addNum(root * 2 + 1,l,n.mid(),v);
  47.         addNum(root * 2 + 2,n.mid() + 1,r,v);
  48.     }
  49. }
  50. long long askSum(int root,int l,int r){
  51.     node &n = t[root];
  52.     if(n.l == l && n.r == r)
  53.         return n.sum + (r - l + 1) * n.inc;
  54.     n.sum += (n.r - n.l + 1) * n.inc;
  55.     addNum(root * 2 + 1,n.l,n.mid(),n.inc);
  56.     addNum(root * 2 + 2,n.mid() + 1,n.r,n.inc);
  57.     n.inc = 0;

  59.     if(l > n.mid())
  60.         return askSum(root * 2 + 2,l,r);
  61.     else if(r <= n.mid())
  62.         return askSum(root * 2 + 1,l,r);
  63.     else{
  64.         return askSum(root * 2 + 1,l,n.mid()) +
  65.         askSum(root * 2 + 2,n.mid() + 1,r);
  66.     }
  67. }
  68. int main(){
  69.     int n,m,c,l,r,v,k;
  70.     cin >> n >> m;
  71.     buildTree(0,1,n);
  72.     for(int i = 1;i <= n;i++){
  73.         cin >> k;
  74.         insertNum(0,i,k);
  75.     }
  76.     for(int i = 1;i <= m;i++){
  77.         cin >> c;
  78.         if(c == 1){
  79.             cin >> l >> r >> k;
  80.             addNum(0,l,r,k);
  81.         }else{
  82.             cin >> l >> r;
  83.             cout << askSum(0,l,r) << endl;
  84.         }
  85.     }
  86.     return 0;
  87. }
复制代码
作者: 吴语林    时间: 2018-7-29 19:30
  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. }
复制代码
作者: walk_alone    时间: 2018-7-29 20:13
  1. #include <cstdio>
  2. long long a[1000001],sum[4000001],tag[4000001];
  3. void build(long long place,long long left,long long right)
  4. {
  5.     if(left==right)
  6.     {
  7.         sum[place]=a[left];
  8.         return;
  9.     }
  10.     long long mid=(left+right)>>1;
  11.     build(place<<1,left,mid);
  12.     build(place<<1|1,mid+1,right);
  13.     sum[place]=sum[place<<1]+sum[place<<1|1];
  14. }
  15. inline void find(long long left,long long right,long long place,long long x)
  16. {
  17.     tag[place]+=x;
  18.     sum[place]+=x*(right-left+1);
  19. }
  20. inline void putdown(long long left,long long right,long long place)
  21. {
  22.     long long mid=(left+right)>>1;
  23.     find(left,mid,place<<1,tag[place]);
  24.     find(mid+1,right,place<<1|1,tag[place]);
  25.     tag[place]=0;
  26. }
  27. inline void change(long long start,long long end,long long left,long long right,long long place,long long x)
  28. {
  29.     if(start<=left && right<=end)
  30.     {
  31.         tag[place]+=x;
  32.         sum[place]+=x*(right-left+1);
  33.         return;
  34.     }   
  35.     putdown(left,right,place);
  36.     long long mid=(left+right)>>1;
  37.     if(start<=mid)
  38.         change(start,end,left,mid,place<<1,x);
  39.     if(end>mid)
  40.         change(start,end,mid+1,right,place<<1|1,x);
  41.     sum[place]=sum[place<<1|1]+sum[place<<1];
  42. }
  43. long long query(long long start,long long end,long long left,long long right,long long place)
  44. {
  45.     long long ans=0;
  46.     if(start<=left && right<=end)
  47.         return ans=sum[place];
  48.     long long mid=(left+right)>>1;
  49.     putdown(left,right,place);
  50.     if(start<=mid)
  51.         ans+=query(start,end,left,mid,place<<1);
  52.     if(end>mid)
  53.         ans+=query(start,end,mid+1,right,place<<1|1);
  54.     return ans;
  55. }
  56. int main()
  57. {
  58.     long long n,m,p,q,x;
  59.     int k;
  60.     scanf("%lld%lld",&n,&m);
  61.     for(int i=1;i<=n;i++)
  62.         scanf("%lld",&a[i]);
  63.     build(1,1,n);
  64.     for(int i=1;i<=m;i++)
  65.     {
  66.         scanf("%d",&k);
  67.         if(k==1)
  68.         {
  69.             scanf("%lld%lld%lld",&p,&q,&x);
  70.             change(p,q,1,n,1,x);
  71.         }

  73.         if(k==2)
  74.         {
  75.             scanf("%lld%lld",&p,&q);
  76.             printf("%lld\n",query(p,q,1,n,1));
  77.         }
  78.     }
  79.     return 0;
  80. }
复制代码
作者: zhwang    时间: 2018-7-30 08:31
  1. #include<cstdio>
  2. #define int long long
  3. int a[100001];
  4. int he;
  5. int n,m,k,l,r,x;
  6. struct node
  7. {
  8.     int left;
  9.     int right;
  10.     int sum;
  11.     int tag;
  12. }tree[400001];
  13. void setup(int root,int start,int end)
  14. {
  15.     tree[root].tag=0;
  16.     tree[root].left=start;
  17.     tree[root].right=end;
  18.     if(start==end)
  19.     {
  20.         tree[root].sum=a[start];
  21.     }
  22.     else
  23.     {
  24.         setup(root*2,start,start+(end-start)/2);
  25.         setup(root*2+1,start+(end-start)/2+1,end);
  26.         tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
  27.     }
  28. }
  29. void add(int start,int end,int root,int num)
  30. {
  31.     if(tree[root].left==start&&tree[root].right==end)
  32.     {
  33.         tree[root].tag+=num;
  34.         return;
  35.     }
  36.     else
  37.     {
  38.         if(end<=tree[root*2].right)
  39.         {
  40.             add(start,end,2*root,num);
  41.         }
  42.         else
  43.         {
  44.             if(start>=tree[root*2+1].left)
  45.             {
  46.                 add(start,end,2*root+1,num);
  47.             }
  48.             else
  49.             {
  50.                 add(start,tree[2*root].right,2*root,num);
  51.                 add(tree[2*root+1].left,end,2*root+1,num);
  52.             }
  53.         }
  54.     }
  55.     tree[2*root].tag+=tree[root].tag;
  56.     tree[2*root+1].tag+=tree[root].tag;
  57.     tree[root].tag=0;
  58.     tree[root].sum=tree[2*root].sum+tree[2*root+1].sum+tree[2*root].tag*(tree[2*root].right-tree[2*root].left+1)+tree[2*root+1].tag*(tree[2*root+1].right-tree[2*root+1].left+1);
  59. }
  60. long long findout(int start,int end,int root)
  61. {
  62.     if (tree[root].left==start&&tree[root].right==end)
  63.     {
  64.         return tree[root].sum+tree[root].tag*(end-start+1);
  65.     }
  66.     long long answer=0;
  67.     tree[2*root].tag+=tree[root].tag;
  68.     tree[2*root+1].tag+=tree[root].tag;
  69.     tree[root].tag=0;
  70.     tree[root].sum=tree[2*root].sum+tree[2*root+1].sum+tree[2*root].tag*(tree[2*root].right-tree[2*root].left+1)+tree[2*root+1].tag*(tree[2*root+1].right-tree[2*root+1].left+1);
  71.     if(start>=tree[root*2+1].left)
  72.     {
  73.         answer=findout(start,end,root*2+1);
  74.     }
  75.     else
  76.     {
  77.         if(end<=tree[root*2].right)
  78.         {
  79.             answer=findout(start,end,root*2);
  80.         }
  81.         else
  82.         {
  83.             answer+=findout(start,tree[root*2].right,root*2);
  84.             answer+=findout(tree[root*2+1].left,end,root*2+1);
  85.         }
  86.     }
  87.     return answer;
  88. }
  89. signed main()
  90. {
  91.     scanf("%lld%lld",&n,&m);
  92.     for(int i=1;i<=n;i++)
  93.     {
  94.         scanf("%lld",&a[i]);
  95.     }
  96.     setup(1,1,n);
  97.     for(int i=1;i<=m;i++)
  98.     {
  99.         scanf("%lld",&k);
  100.         if(k==1)
  101.         {
  102.             scanf("%lld%lld%lld",&l,&r,&x);
  103.             add(l,r,1,x);
  104.         }
  105.         else
  106.         {
  107.             if(k==2)
  108.             {
  109.                 scanf("%lld%lld",&l,&r);
  110.                 printf("%lld\n",findout(l,r,1));
  111.             }
  112.         }
  113.     }
  114.     return 0;
  115. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-10-4 13:49
  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. }
复制代码




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