fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 10000000
  5. long int arr[1000000];
  6.  
  7. long int tree[MAX] ;  // To store segment tree
  8. long int lazy[MAX] ;  // To store pending updates
  9.  
  10. void updateRangeUtil(long int si, long int ss, long int se, long int us,
  11.                      long int ue, long int diff)
  12. {
  13.  
  14.     if (lazy[si] != 0)
  15.     {
  16.  
  17.         tree[si] += (se-ss+1)*lazy[si];
  18.  
  19.         if (ss != se)
  20.         {
  21.  
  22.             lazy[si*2 + 1]   += lazy[si];
  23.             lazy[si*2 + 2]   += lazy[si];
  24.         }
  25.  
  26.         lazy[si] = 0;
  27.     }
  28.  
  29.  
  30.     if (ss>se || ss>ue || se<us)
  31.         return ;
  32.  
  33.     // Current segment is fully in range
  34.     if (ss>=us && se<=ue)
  35.     {
  36.         // Add the difference to current node
  37.         tree[si] += (se-ss+1)*diff;
  38.  
  39.         // same logic for checking leaf node or not
  40.         if (ss != se)
  41.         {
  42.  
  43.             lazy[si*2 + 1]   += diff;
  44.             lazy[si*2 + 2]   += diff;
  45.         }
  46.         return;
  47.     }
  48.  
  49.     // If not completely in rang, but overlaps, recur for
  50.     // children,
  51.     int mid = (ss+se)/2;
  52.     updateRangeUtil(si*2+1, ss, mid, us, ue, diff);
  53.     updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);
  54.  
  55.     // And use the result of children calls to update this
  56.     // node
  57.     tree[si] = tree[si*2+1] + tree[si*2+2];
  58. }
  59.  
  60. void updateRange(long int n, long int us, long int ue, long int diff)
  61. {
  62.    updateRangeUtil(0, 0, n-1, us, ue, diff);
  63. }
  64.  
  65.  
  66. long int getSumUtil(long int ss, long int se, long int qs,long int qe, long int si)
  67. {
  68.  
  69.     if (lazy[si] != 0)
  70.     {
  71.  
  72.         tree[si] += (se-ss+1)*lazy[si];
  73.  
  74.         // checking if it is not leaf node because if
  75.         // it is leaf node then we cannot go further
  76.         if (ss != se)
  77.         {
  78.             // Since we are not yet updating children os si,
  79.             // we need to set lazy values for the children
  80.             lazy[si*2+1] += lazy[si];
  81.             lazy[si*2+2] += lazy[si];
  82.         }
  83.  
  84.         // unset the lazy value for current node as it has
  85.         // been updated
  86.         lazy[si] = 0;
  87.     }
  88.  
  89.     // Out of range
  90.     if (ss>se || ss>qe || se<qs)
  91.         return 0;
  92.  
  93.     // At this point we are sure that pending lazy updates
  94.     // are done for current node. So we can return value
  95.     // (same as it was for query in our previous post)
  96.  
  97.     // If this segment lies in range
  98.     if (ss>=qs && se<=qe)
  99.         return tree[si];
  100.  
  101.     // If a part of this segment overlaps with the given
  102.     // range
  103.     int mid = (ss + se)/2;
  104.     return getSumUtil(ss, mid, qs, qe, 2*si+1) +
  105.            getSumUtil(mid+1, se, qs, qe, 2*si+2);
  106. }
  107.  
  108. // Return sum of elements in range from index qs (quey
  109. // start) to qe (query end).  It mainly uses getSumUtil()
  110. long int getSum(long int n, long int qs,long int qe)
  111. {
  112.     // Check for erroneous input values
  113.     if (qs < 0 || qe > n-1 || qs > qe)
  114.     {
  115.        // printf("Invalid Input");
  116.         return -1;
  117.     }
  118.  
  119.     return getSumUtil(0, n-1, qs, qe, 0);
  120. }
  121.  
  122. // A recursive function that constructs Segment Tree for
  123. //  array[ss..se]. si is index of current node in segment
  124. // tree st.
  125. void constructSTUtil(long int arr[], long int ss, long int se, long int si)
  126. {
  127.     // out of range as ss can never be greater than se
  128.     if (ss > se)
  129.         return ;
  130.  
  131.     // If there is one element in array, store it in
  132.     // current node of segment tree and return
  133.     if (ss == se)
  134.     {
  135.         tree[si] = arr[ss];
  136.         return;
  137.     }
  138.  
  139.     int mid = (ss + se)/2;
  140.     constructSTUtil(arr, ss, mid, si*2+1);
  141.     constructSTUtil(arr, mid+1, se, si*2+2);
  142.  
  143.     tree[si] = tree[si*2 + 1] + tree[si*2 + 2];
  144. }
  145.  
  146. void constructST(long int arr[], long int n)
  147. {
  148.     // Fill the allocated memory st
  149.     constructSTUtil(arr, 0, n-1, 0);
  150. }
  151.  
  152. int main()
  153. {
  154.  
  155.     long int n,m,c,q,u,v,k;
  156.     char ch;
  157.     scanf("%ld%ld%ld",&n,&m,&c);
  158.  
  159.     memset(arr,c,n*sizeof(long int));
  160.  
  161.     constructST(arr, n);
  162.     while(m--)
  163.     {
  164.  while ((getchar()) != '\n');
  165.         scanf("%c",&ch);
  166.  
  167.       if(ch=='Q')
  168.       {
  169.           scanf("%ld",&q);
  170.           printf("%ld\n",getSum(n, q-1, q-1));
  171.       }
  172.        else if(ch=='S')
  173.        {   scanf("%ld%ld%ld",&u,&v,&k);
  174.            updateRange(n, u-1, v-1, k);
  175.        }
  176.     }
  177.     return 0;
  178. }
Success #stdin #stdout 0s 179328KB
comments (?)
stdin
copy 
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
stdout
copy 
0
1
2
https://ideone.com/dBAHaU
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

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!