fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC optimize("unroll-loops")
  7. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  8. #define ordered_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
  9. #define down '\n'
  10. #define lli long long int
  11. #define ulli unsigned long long int
  12. #define ld long double
  13. using namespace std;
  14. using namespace __gnu_pbds;
  15. struct node
  16. {
  17.     int first_val,second_val;
  18.     node() { first_val = second_val = INT_MIN; }
  19.  
  20. };
  21. const int maxn = 1e6+100;
  22. const node EMPTY;
  23.  
  24. int n,q,a[maxn];
  25. node sg[maxn*4];
  26. void build_tree( int id , int left , int right )
  27. {
  28.     if( left == right )
  29.     {
  30.         sg[id].first_val = a[left];
  31.         return;
  32.     }
  33.     int mid = ( left + right )/2, leftt =  id*2, rightt = id*2+1;
  34.     build_tree(leftt,left,mid);
  35.     build_tree(rightt,mid+1,right);
  36.     sg[id].first_val  = max( sg[leftt].first_val , sg[rightt].first_val );
  37.     sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) );
  38. }
  39. void update_tree( int id , int left , int right , int pos , int val )
  40. {
  41.     if( right < pos || left > pos )return;
  42.     if( left == right )
  43.     {
  44.         sg[id].first_val = val;
  45.         return;
  46.     }
  47.     int mid = ( left + right )/2, leftt =  id*2, rightt = id*2+1;
  48.     update_tree(leftt,left,mid,pos,val);
  49.     update_tree(rightt,mid+1,right,pos,val);
  50.     sg[id].first_val  = max( sg[leftt].first_val , sg[rightt].first_val );
  51.     sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) );
  52. }
  53. node query_tree( int id , int left , int right, int u , int v )
  54. {
  55.     if( left > v || right < u ) return EMPTY;
  56.     if( left >= u && right <= v )return sg[id];
  57.  
  58.     int mid = ( left + right )/2;
  59.     node leftt  =  query_tree(id*2,left,mid,u,v);
  60.     node rightt =  query_tree(id*2+1,mid+1,right,u,v);
  61.     node ans;
  62.     ans.first_val  = max( leftt.first_val , rightt.first_val );
  63.     ans.second_val = max( min( leftt.first_val , rightt.first_val) , max( leftt.second_val , rightt.second_val ) );
  64.     return ans;
  65. }
  66. void read()
  67. {
  68. 	cin >> n >> q;
  69. 	for( int i =1 ; i <= n; i ++ ) cin >> a[i];
  70. 	build_tree(1,1,n);
  71. }
  72. void solve()
  73. {
  74.     int type, left, right, pos, val;
  75.     while( q -- )
  76.     {
  77.         cin >> type;
  78.         if( type == 1 )
  79.         {
  80.             cin >> pos >> val;
  81.             update_tree(1,1,n,pos,val);
  82.         }
  83.         else
  84.         {
  85.             cin >> left >> right;
  86.             node ans = query_tree(1,1,n,left,right);
  87.             cout << ( ans.first_val + ans.second_val)  << " ";
  88.         }
  89.     }
  90. }
  91. int main()
  92. {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(nullptr);
  95.     read();
  96.     solve();
  97.     return 0;
  98. }
  99.  
Runtime error #stdin #stdout 0.72s 2095840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ezsOSe
language:
C++14 (gcc 8.3)
created:
2 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!