fork download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<string.h>
  5.  
  6. using namespace std;
  7. #define ll long long
  8. #define MAX 100005
  9.  
  10. struct node{
  11.     ll sum,upval;
  12.     bool up;
  13.     node():sum(0),upval(0),up(false){}
  14.     node(ll a):sum(a),upval(0),up(false){}
  15.     void merge(node a,node b){
  16.         sum = a.sum+b.sum;
  17.     }
  18.     void pass(int len,int v){
  19.         sum +=(len*v);
  20.         upval +=v;
  21.         up = true;
  22.     }
  23. };
  24.  
  25. node segtree[4*MAX];
  26.  
  27. void build(int t,int i,int j){
  28.     if(i==j){
  29.         segtree[t] = node();
  30.         return;
  31.     }
  32.     int l=2*t,mid=(i+j)/2;
  33.     build(l,i,mid);
  34.     build(l+1,mid+1,j);
  35. }
  36.  
  37. void update(int t,int i,int j,int ri,int rj,int v){
  38.     if(ri<=i && rj>=j){
  39.         segtree[t].pass((j-i+1),v);
  40.         return;
  41.     }
  42.     if(j<ri || i>rj)
  43.         return;
  44.     int l=2*t,mid=(i+j)/2;
  45.     update(l,i,mid,ri,rj,v);
  46.     update(l+1,mid+1,j,ri,rj,v);
  47.     segtree[t].merge(segtree[l],segtree[l+1]);
  48.  
  49. }
  50.  
  51. ll query(int t,int i,int j,int ri,int rj){
  52.     if(ri<=i && rj>=j)
  53.         return segtree[t].sum;
  54.     if(j<ri || i>rj)
  55.         return 0;
  56.     int l=2*t,mid=(i+j)/2;
  57.     if(segtree[t].up){
  58.         segtree[l].pass((mid-i+1),segtree[t].upval);
  59.         segtree[l+1].pass((j-mid),segtree[t].upval);
  60.         segtree[t].upval=0;
  61.         segtree[t].up = false;
  62.     }
  63.     return query(l,i,mid,ri,rj)+query(l+1,mid+1,j,ri,rj);
  64. }
  65.  
  66.  
  67.  
  68. int main() {
  69. 	int t,n,c,a,p,q,v;
  70.     scanf("%d",&t);
  71.     while(t--){
  72.         scanf("%d%d",&n,&c);
  73.         //build(1,1,2*pow(2,log2(n)+1));
  74.         while(c--){
  75.             scanf("%d%d%d",&a,&p,&q);
  76.             if(a==0){
  77.                 scanf("%d",&v);
  78.                 update(1,1,n,p,q,v);
  79.             }
  80.             else if(a==1)
  81.                 printf("%lld\n",query(1,1,n,p,q));
  82.         }
  83.         memset(segtree,0,sizeof(segtree));
  84.     }
  85. 	return 0;
  86. }
Success #stdin #stdout 0.01s 10544KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
Standard output is empty
https://ideone.com/arYXRl
horrible
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!