fork(5) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. template<typename node_const_iterator, typename node_iterator, typename cmp_fn,
  8. 	   typename _Alloc>
  9. struct tree_max
  10. {
  11.     typedef int metadata_type;
  12.  
  13.     tree_max(){}
  14.  
  15.     inline void operator() (node_iterator it, node_const_iterator null) const
  16.     {
  17.         int mx = (*it)->second;
  18.         if (it.get_l_child() != null)
  19.             mx = max(mx, it.get_l_child().get_metadata());
  20.         if (it.get_r_child() != null)
  21.             mx = max(mx, it.get_r_child().get_metadata());
  22.         (int&)(it.get_metadata()) = mx;
  23.     }
  24. };
  25.  
  26. typedef tree<int, int, less<int>, splay_tree_tag, tree_max> Tree;
  27.  
  28. Tree A; 
  29.  
  30. int main()
  31. {
  32.     int n;
  33.     scanf("%d", &n);
  34.     for (int i = 1; i <= n; i++)
  35.     {
  36.         int t;
  37.         scanf("%d", &t);
  38.         A.insert(make_pair(i, t));
  39.     }
  40.     int m;
  41.     scanf("%d", &m);
  42.     for (int i = 0; i < m; i++)
  43.     {
  44.         char t;
  45.         int x, y;
  46.         scanf(" %c %d %d", &t, &x, &y);
  47.         if (t == 'u')
  48.         {
  49.             A.erase(x);
  50.             A.insert(make_pair(x, y));
  51.         }
  52.         else
  53.         {
  54.             Tree B, C;
  55.             A.split(y, C);
  56.             A.split(x - 1, B);
  57.             printf("%d ", B.node_begin().get_metadata());
  58.             A.join(B);
  59.             A.join(C);
  60.         }
  61.     }
  62. }
  63.  
  64.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
5
1 2 3 4 5
5
s 1 5
u 3 10
s 1 5
u 2 12
s 1 3
stdout
copy 
5 10 12
https://ideone.com/jOxlgl
language:
C++ (gcc 8.3)
created:
10 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!