fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fr(a,b) for(int i = a; i < b; i++)
  4. using namespace std;
  5.  
  6. #define left(i) (2*i + 1)
  7. #define right(i) (2*i + 2)
  8. #define parent(i) ((i-1)/2)
  9.  
  10. template<class T>
  11. class SegmentTree
  12. {
  13.     public:
  14.         //tree constructors.
  15.         SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  16.         SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  17.  
  18.         //query the range l to r, 0 based array indexing.
  19.         T query(int l, int r);
  20.  
  21.         //update the element at index idx to val.
  22.         void update(int idx, T val);
  23.         ///TODO lazy propagation
  24.     private:
  25.         //represents the segment tree.
  26.         T *tree;
  27.  
  28.         //builds the segment tree.
  29.         void buildTree(std::vector<T> data);
  30.  
  31.         //size of the segment tree array.
  32.         int segTreeSize;
  33.  
  34.         //extra nodes must be added to array to make its size a power of 2
  35.         //this is the value to be filled for the those nodes.
  36.         T valueForExtraNodes;
  37.  
  38.         //specifies how to combine child node results to form parent node result.
  39.         T (*combine)(T obj1, T obj2);
  40.  
  41.         //used to calculate the size of array needed to store the tree.
  42.         int calculateSize(int n);
  43.  
  44.         //helps to solve a range query.
  45.         T queryHelper(int l,int r, int st, int ed, int node);
  46. };
  47.  
  48. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  49.                                                 T value, T (*combine)(T obj1, T obj2))
  50. {
  51.    this->combine = combine;
  52.    valueForExtraNodes = value;
  53.    segTreeSize = calculateSize(data.size());
  54.    buildTree(data);
  55. }
  56.  
  57. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  58.                                             T value, T (*combine)(T obj1, T obj2))
  59. {
  60.    this->combine = combine;
  61.    valueForExtraNodes = value;
  62.    segTreeSize = calculateSize(n);
  63.  
  64.    std::vector<T> data;
  65.    for(int i = 0; i < n; i++)
  66.          data.push_back(ar[i]);
  67.  
  68.    buildTree(data);
  69. }
  70.  
  71.  
  72. template<class T> int SegmentTree<T>::calculateSize(int n)
  73. {
  74.     int pow2 = 1;
  75.     while( pow2 < n)
  76.     {
  77.         pow2 = pow2 << 1;
  78.     }
  79.     return 2*pow2 - 1;
  80. }
  81.  
  82. template<class T> T SegmentTree<T>::query(int l, int r)
  83. {
  84.     int st = 0, ed = segTreeSize/2;
  85.     return queryHelper(l, r, st, ed, 0);
  86. }
  87.  
  88. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  89. {
  90.     if( (r < st) || (l > ed) || (l > r) )
  91.         return valueForExtraNodes;
  92.     if(st >= l && ed <= r)
  93.         return tree[node];
  94.     T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  95.     T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  96.     return combine(leftVal, rightVal);
  97. }
  98.  
  99. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  100. {
  101.    int n = data.size();
  102.    tree = new T[segTreeSize];
  103.    int extraNodes = (segTreeSize/2 + 1) - n;
  104.    for(int i = segTreeSize - 1; i >= 0; i--)
  105.    {
  106.        if(extraNodes>0)
  107.            {
  108.                tree[i] = valueForExtraNodes;
  109.                extraNodes--;
  110.            }
  111.        else if(n>0)
  112.            {
  113.                tree[i] = data[n-1];
  114.                n--;
  115.            }
  116.        else
  117.            tree[i] = combine(tree[left(i)], tree[right(i)]);
  118.    }
  119. }
  120.  
  121. template<class T> void SegmentTree<T>::update(int idx, T val)
  122. {
  123.     int segTreeIdx = (segTreeSize/2) + idx;
  124.     tree[segTreeIdx] = val;
  125.     while(parent(segTreeIdx) >= 0)
  126.     {
  127.         segTreeIdx = parent(segTreeIdx);
  128.         if(right(segTreeIdx) < segTreeSize)
  129.           tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  130.         if(segTreeIdx == 0)
  131.             break;
  132.     }
  133. }
  134.  
  135. struct node
  136. {
  137.     node(int x, int y):m1(x),m2(y){}
  138.     node(){}
  139.     int m1, m2;
  140. };
  141.  
  142. node combine(node x, node y)
  143. {
  144.     node temp;
  145.     vector<int> s = {x.m1,x.m2,y.m1,y.m2};
  146.     sort(s.begin(),s.end(),greater<int>());
  147.     temp.m1 = s[0];
  148.     temp.m2 = s[1];
  149.     return temp;
  150. }
  151.  
  152. int main(){
  153.  
  154.     int n,i,j,q;
  155.     cin>>n;
  156.     vector<node> ar(n);
  157.  
  158.     for(int i = 0; i < n; i++)
  159.     {
  160.         cin>>ar[i].m1;
  161.         ar[i].m2 = INT_MIN;
  162.     }
  163.     node smallest(INT_MIN, INT_MIN);
  164.  
  165.     SegmentTree<node> sg(ar, smallest, combine);
  166.  
  167.     cin>>q;
  168.     while(q--)
  169.     {
  170.         char ch;
  171.         int x,y;
  172.         cin>>ch>>x>>y;
  173.         if(ch == 'Q')
  174.         {
  175.             node ans = sg.query(x-1,y-1);
  176.             cout<<ans.m1+ans.m2<<'\n';
  177.         }
  178.         else
  179.         {
  180.             node upd(y, INT_MIN);
  181.             sg.update(x-1, upd);
  182.         }
  183.     }
  184.     return 0;
  185. }
  186.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5
stdout
copy 
7
9
11
12
https://ideone.com/fUK5Jz
language:
C++14 (gcc 8.3)
created:
5 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!