#511. ITQPMAX – Truy vấn cặp lớn nhất

bài này thi segment tree mỗi node lưu 2 giá trị first là giá trị lớn nhất còn second là là giá trị lớn thứ 2 trong đoạn từ left tới right mà node quản lí thì khi hợp 2 node trái và phải thì giá trị lớn nhất( first ) = max( của cả 2 node ) còn giá trị lớn thứ 2= max ( min( left.first , right.first) , max( left.second, rightt.second ) )

https://ideone.com/ezsOSe

#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update> #define ordered_multiset tree<int,null_type,less_equal,rb_tree_tag,tree_order_statistics_node_update> #define down '\n' #define lli long long int #define ulli unsigned long long int #define ld long double using namespace std; using namespace __gnu_pbds; struct node { int first_val,second_val; node() { first_val = second_val = INT_MIN; }

}; const int maxn = 1e6+100; const node EMPTY;

int n,q,a[maxn]; node sg[maxn4]; void build_tree( int id , int left , int right ) { if( left == right ) { sg[id].first_val = a[left]; return; } int mid = ( left + right )/2, leftt = id2, rightt = id2+1; build_tree(leftt,left,mid); build_tree(rightt,mid+1,right); sg[id].first_val = max( sg[leftt].first_val , sg[rightt].first_val ); sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) ); } void update_tree( int id , int left , int right , int pos , int val ) { if( right < pos || left > pos )return; if( left == right ) { sg[id].first_val = val; return; } int mid = ( left + right )/2, leftt = id2, rightt = id*2+1; update_tree(leftt,left,mid,pos,val); update_tree(rightt,mid+1,right,pos,val); sg[id].first_val = max( sg[leftt].first_val , sg[rightt].first_val ); sg[id].second_val = max( min( sg[leftt].first_val , sg[rightt].first_val) , max( sg[leftt].second_val , sg[rightt].second_val ) ); } node query_tree( int id , int left , int right, int u , int v ) { if( left > v || right < u ) return EMPTY; if( left >= u && right <= v )return sg[id];

int mid = ( left + right )/2;
node leftt  =  query_tree(id*2,left,mid,u,v);
node rightt =  query_tree(id*2+1,mid+1,right,u,v);
node ans;
ans.first_val  = max( leftt.first_val , rightt.first_val );
ans.second_val = max( min( leftt.first_val , rightt.first_val) , max( leftt.second_val , rightt.second_val ) );
return ans;

} void read() { cin >> n >> q; for( int i =1 ; i <= n; i ++ ) cin >> a[i]; build_tree(1,1,n); } void solve() { int type, left, right, pos, val; while( q -- ) { cin >> type; if( type == 1 ) { cin >> pos >> val; update_tree(1,1,n,pos,val); } else { cin >> left >> right; node ans = query_tree(1,1,n,left,right); cout << ( ans.first_val + ans.second_val) << " "; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); return 0; }

mình có code ac nè