fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(i,a,b) for(i=a;i<b;i++)
  3. #define rep(i,n) REP(i,0,n)
  4. #define ll long long
  5. #define ull unsigned ll
  6. #define MAX 100005
  7. #define gc getchar_unlocked
  8. using namespace std;
  9. ll tree[4*MAX],lazy[4*MAX];
  10. inline void scanl(ll &x)
  11. {
  12.     register int c = gc();
  13.     x = 0;
  14.     int neg = 0;
  15.     for(;((c<48 || c>57) && c != '-');c = gc());
  16.     if(c=='-') {neg=1;c=gc();}
  17.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  18.     if(neg) x=-x;
  19. }
  20. inline void scan(int &x)
  21. {
  22.     register int c = gc();
  23.     x = 0;
  24.     int neg = 0;
  25.     for(;((c<48 || c>57) && c != '-');c = gc());
  26.     if(c=='-') {neg=1;c=gc();}
  27.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  28.     if(neg) x=-x;
  29. }
  30. inline void fastWrite(ll a)
  31. {
  32.     char snum[20];
  33.     int i=0;
  34.     do
  35.     {
  36.         snum[i++]=a%10+48;
  37.         a=a/10;
  38.     }
  39.     while(a!=0);
  40.     i=i-1;
  41.     while(i>=0)
  42.         putchar_unlocked(snum[i--]);
  43.     putchar_unlocked('\n');
  44. }
  45. void update_tree(int node,int a,int b,int i,int j,ll val)
  46. {
  47.     if(lazy[node]!=0)  
  48.     {
  49.         tree[node]+=lazy[node]; 
  50.         if(a!=b)
  51.         {
  52.             lazy[node*2]+=lazy[node];   
  53.             lazy[node*2+1]+=lazy[node];
  54.         }
  55.         lazy[node]=0;
  56.     }
  57.     if(a>b || a>j || b<i)  
  58.         return;
  59.     if(a>=i && b<=j)
  60.     {
  61.         tree[node]+=val;
  62.         if(a!=b)
  63.         {
  64.             lazy[node*2]+=val;
  65.             lazy[node*2+1]+=val;
  66.         }
  67.         return;
  68.     }
  69.     update_tree(node*2,a,(a+b)/2,i,j,val);
  70.     update_tree(node*2+1,(a+b)/2+1,b,i,j,val);
  71.     tree[node]=(tree[node*2]+tree[node*2+1]);
  72. }
  73. ll query_tree(int node,int a,int b,int i,int j)
  74. {
  75.     if(a>b || a>j || b<i)
  76.         return 0;
  77.     if(lazy[node]!=0)
  78.     {
  79.         tree[node]+=lazy[node];
  80.         if(a!=b)
  81.         {
  82.             lazy[node*2]+=lazy[node];
  83.             lazy[node*2+1]+=lazy[node];
  84.         }
  85.         lazy[node]=0;
  86.     }
  87.     if(a==b)
  88.     {
  89.         return tree[node];
  90.     }
  91.     return query_tree(node*2,a,(a+b)/2,i,j)+query_tree(node*2+1,(a+b)/2+1,b,i,j);
  92. }
  93. int main()
  94. {
  95.     int t,i,n,c,ch,l,r;
  96.     ll val;
  97.     scan(t);
  98.     while(t--)
  99.     {
  100.         scan(n);
  101.         scan(c);
  102.         while(c--)
  103.         {   
  104.             scan(ch);
  105.             scan(l);
  106.             scan(r);
  107.             --l;--r;
  108.             if(ch==0)
  109.             {
  110.                 scanl(val);
  111.                 update_tree(1,0,n-1,l,r,val);
  112.             }
  113.             else
  114.             {
  115.                 printf("%lld\n",query_tree(1,0,n-1,l,r));
  116.             }
  117.         }
  118.     }
  119.     return 0;
  120. }
Success #stdin #stdout 0s 9400KB
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 
80
508
https://ideone.com/egRSXh
language:
C++14 (gcc 8.3)
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!