fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N= 100005;
  5.  
  6. struct node{
  7.     int maxPrefix;
  8.     int maxSuffix;
  9.     int ans;
  10.     long left;
  11.     long right;
  12.  
  13.     void assignLeaf( long val ){
  14.         maxPrefix= maxSuffix= ans= 1;
  15.         left= right= val;
  16.     }
  17.  
  18.     void merge( node a, node b ){
  19.  
  20.         this->left= a.left;
  21.         this->right= b.right;
  22.         this->maxPrefix= a.maxPrefix;
  23.         this->maxSuffix= b.maxSuffix;
  24.  
  25.         if( a.right < b.left ){
  26.             this->ans= max( maxSuffix+maxPrefix, max( maxPrefix, maxSuffix ) );
  27.         }else{
  28.             this->ans= max( a.ans, b.ans );
  29.         }
  30.  
  31.     }
  32. };
  33.  
  34. node st[4*N];
  35. long a[N];
  36.  
  37. void build( int id, int l, int r ){
  38.  
  39.     if( l== r ){
  40.         st[id].assignLeaf( a[l] );
  41.         return ;
  42.     }
  43.  
  44.     int mid= l + ( r-l )/2;
  45.  
  46.     build( 2*id, l, mid );
  47.     build( 2*id+1, mid+1, r );
  48.  
  49.     st[id].merge( st[id*2], st[id*2+1] );
  50.  
  51. }
  52.  
  53. int query( int id, int l, int r, int x, int y ){
  54.  
  55.     if( l > r || y < l || x > r )
  56.         return 0;
  57.  
  58.     if( x<= l && y >= r )
  59.         return st[id].ans;
  60.  
  61.     int mid= l + ( r-l )/2;
  62.  
  63.     int a= query( 2*id, l, mid, x, y );
  64.     int b= query( 2*id+1, mid+1, r , x, y );
  65.  
  66.     return max( a, b );
  67. }
  68.  
  69. void update( int id, int l, int r, int x , long val ){
  70.  
  71.     if( l== r ){
  72.         a[x]= val;
  73.         st[id].assignLeaf( val );
  74.         return ;
  75.     }
  76.  
  77.     int mid= l + ( r-l )/2;
  78.  
  79.     if( mid >= l && x <= mid )
  80.         update( 2*id, l, mid, x, val );
  81.     else
  82.         update( 2*id+1, mid+1, r, x, val );
  83.  
  84.     st[id].merge( st[id*2], st[id*2+1] );
  85.  
  86. }
  87.  
  88. int main(){
  89.  
  90.     int n, x, y, t, p, q;
  91.  
  92.     cin >> t;
  93.  
  94.     while( t-- ){
  95.  
  96.         cin >> n >> q;
  97.  
  98.         for( int i= 0; i< n; ++i )
  99.             cin >> a[i];
  100.  
  101.         build( 1, 0, n-1 );
  102.  
  103.         while( q-- ){
  104.  
  105.             cin >> p >> x >> y;
  106.  
  107.             if( p ){
  108.                 update( 1, 0, n-1, x, y );
  109.             }else{
  110.                 cout << query( 1, 0, n-1, x, y );
  111.             }
  112.  
  113.         }
  114.  
  115.  
  116.  
  117.     }
  118.  
  119. }
  120.  
Success #stdin #stdout 0s 11664KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HjMJQi
language:
C++ (gcc 8.3)
created:
8 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!