fork download
copy 
  1. /*
  2.     author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  6. #define ll long long
  7. using namespace std;
  8. #define left(i) (2*i + 1)
  9. #define right(i) (2*i + 2)
  10. #define parent(i) ((i-1)/2)
  11. #include <vector>
  12.  
  13. template<class T>
  14. class SegmentTree
  15. {
  16.     public:
  17.         SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  18.         SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  19.         T query(int l, int r);
  20.         void update(int idx, T val);
  21.         //TODO lazy propagation
  22.     private:
  23.         T *tree;
  24.         void buildTree(std::vector<T> data);
  25.         int segTreeSize;
  26.         T valueForExtraNodes;
  27.         T (*combine)(T obj1, T obj2);
  28.         int calculateSize(int n);
  29.         T queryHelper(int l,int r, int st, int ed, int node);
  30. };
  31.  
  32. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  33.                                                 T value, T (*combine)(T obj1, T obj2))
  34. {
  35.    this->combine = combine;
  36.    valueForExtraNodes = value;
  37.    segTreeSize = calculateSize(data.size());
  38.    buildTree(data);
  39. }
  40.  
  41. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  42.                                             T value, T (*combine)(T obj1, T obj2))
  43. {
  44.    this->combine = combine;
  45.    valueForExtraNodes = value;
  46.    segTreeSize = calculateSize(n);
  47.  
  48.    std::vector<T> data;
  49.    for(int i = 0; i < n; i++)
  50.          data.push_back(ar[i]);
  51.  
  52.    buildTree(data);
  53. }
  54.  
  55.  
  56. template<class T> int SegmentTree<T>::calculateSize(int n)
  57. {
  58.     int pow2 = 1;
  59.     while( pow2 < n)
  60.     {
  61.         pow2 = pow2 << 1;
  62.     }
  63.     return 2*pow2 - 1;
  64. }
  65.  
  66. template<class T> T SegmentTree<T>::query(int l, int r)
  67. {
  68.     int st = 0, ed = segTreeSize/2;
  69.     return queryHelper(l, r, st, ed, 0);
  70. }
  71.  
  72. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  73. {
  74.     if( (r < st) || (l > ed) || (l > r) )
  75.         return valueForExtraNodes;
  76.     if(st >= l && ed <= r)
  77.         return tree[node];
  78.     T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  79.     T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  80.     return combine(leftVal, rightVal);
  81. }
  82.  
  83. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  84. {
  85.    int n = data.size();
  86.    tree = new T[segTreeSize];
  87.    int extraNodes = (segTreeSize/2 + 1) - n;
  88.    for(int i = segTreeSize - 1; i >= 0; i--)
  89.    {
  90.        if(extraNodes>0)
  91.            {
  92.                tree[i] = valueForExtraNodes;
  93.                extraNodes--;
  94.            }
  95.        else if(n>0)
  96.            {
  97.                tree[i] = data[n-1];
  98.                n--;
  99.            }
  100.        else
  101.            tree[i] = combine(tree[left(i)], tree[right(i)]);
  102.    }
  103. }
  104.  
  105. template<class T> void SegmentTree<T>::update(int idx, T val)
  106. {
  107.     int segTreeIdx = (segTreeSize/2) + idx;
  108.     tree[segTreeIdx] = val;
  109.     while(parent(segTreeIdx) >= 0)
  110.     {
  111.         segTreeIdx = parent(segTreeIdx);
  112.         if(right(segTreeIdx) < segTreeSize)
  113.           tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  114.         if(segTreeIdx == 0)
  115.             break;
  116.     }
  117. }
  118.  
  119. // SEGMENT TREE NODE WITH REQUIRED INFO
  120. struct node
  121. {
  122.     ll maxSumSub;
  123.     ll sumOfAllElements;
  124.     ll prefix;
  125.     ll suffix;
  126.     node(){}
  127.     // For a leaf node, all these values are simply equal to A[x] if
  128.     // node represents range [x,x]
  129.     node(ll val)
  130.         {maxSumSub = sumOfAllElements = prefix = suffix = val;}
  131. };
  132.  
  133. //Generate result for parent node using child nodes.
  134. node combine(node x,node y)
  135. {
  136.     node *ptr = new node();
  137.     // either left ans or right ans
  138.     ptr->maxSumSub = max(x.maxSumSub, y.maxSumSub);
  139.     // or of form suffix UNION prefix
  140.     ptr->maxSumSub = max(ptr->maxSumSub, x.suffix + y.prefix);
  141.     // as discussed
  142.     ptr->prefix = max(x.prefix, x.sumOfAllElements + y.prefix);
  143.     // as discussed
  144.     ptr->suffix = max(y.suffix, y.sumOfAllElements + x.suffix);
  145.     // sum of all elements of range [l,mid] and that of [mid+1,r]
  146.     ptr->sumOfAllElements = x.sumOfAllElements + y.sumOfAllElements;
  147.     return *ptr;
  148. }
  149.  
  150. int main()
  151. {
  152.     fast_io;
  153.     int t,i,j,n,ans,q;
  154.  
  155.     cin>>n>>q;
  156.     vector<node> v(n);
  157.  
  158.     for(i=0;i<n;i++)
  159.     {
  160.         cin>>j;
  161.         v[i] = node(j);
  162.     }
  163.  
  164.     // combine( node_x, identityNode ) = node_x
  165.     // the problem says empty subarrays are allowed
  166.     // The minimum sum will be 0
  167.     node identityNode(0);
  168.     SegmentTree<node> sg(v,identityNode,combine);
  169.  
  170.     while(q--)
  171.     {
  172.         cin>>i>>j;
  173.         sg.update(i-1,j);
  174.         node as = sg.query(0,n-1);
  175.         cout<<(as.maxSumSub)<<'\n';
  176.     }
  177.     return 0;
  178. }
  179.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
5 3
1 2 -3 5 -1
2 6
3 1
2 -2
stdout
copy 
9
13
6
https://ideone.com/MhVmBs
language:
C++14 (gcc 8.3)
created:
3 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!