Untitled
unknown
plain_text
a year ago
3.3 kB
3
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define all(v) (v).begin() , (v).end() #define nn "\n" #define ex exit(0); #define sz(s) (int)(s).size() int n ,a , b , t ; const int N = 1e6; int q[N] , s[N]; ll bit , k , res , ans , cnt , sum = 0 ; ll y ; char pp[21][21]; ll lcm(ll x , ll y ){ return x/__gcd(x , y )*y; } bool check(ll x , ll w , ll h , int n ){ if(x/w>=n || x/h>=n){ return 1 ; } if(x/w*x/h>=n){ return 1; } else return 0; } const int K = 1e6; pair<int , int >p[400004]; void build(int v , int l , int r ){ if(l==r){ p[v].first = q[v]; p[v].second = 1 ; return ; } else { int m = (l+r)/2; build(v*2 ,l , m ); build(v*2+1 , m+1 , r ); if(p[v*2].first< p[v*2+1].first){ p[v].first = p[v*2].first; p[v].second = p[v*2].second; } if(p[v*2+1].first< p[v*2].first){ p[v].first = p[v*2+1].first; p[v].second = p[v*2+1].second; } else { p[v].first = p[v*2].first; p[v].second= p[v*2].second+p[v*2+1].second; } } } pair<int, int>get(int v , int tl , int tr , int l , int r ){ if(tl<=l && r <=tr){ return pair<int , int >(p[v].first , p[v].second); } else { int m = (l+r)/2; if(p[v*2].first< p[v*2+1].first){ p[v].first = p[v*2].first; p[v].second = p[v*2].second; } else if(p[v*2+1].first< p[v*2].first){ p[v].first = p[v*2+1].first; p[v].second = p[v*2+1].second; } else { p[v].first = p[v*2].first; p[v].second= p[v*2].second+p[v*2+1].second; } return pair<int , int>(p[v].first , p[v].second); } } void update(int v , int x , int pos , int l , int r ){ if(l==r){ p[v].first = x; p[v].second = 1 ; } else { int m = (l+r)/2; if(pos<=m){ update(v*2 , x , pos , l , m ); } else { update(v*2+1 , x , pos , m+1 , r ); } if(p[v*2].first< p[v*2+1].first){ p[v].first = p[v*2].first; p[v].second = p[v*2].second; } if(p[v*2+1].first< p[v*2].first){ p[v].first = p[v*2+1].first; p[v].second = p[v*2+1].second; } else { p[v].first = p[v*2].first; p[v].second= p[v*2].second+p[v*2+1].second; } } } int main() { ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); //freopen("sum2.in" , "r", stdin); //freopen("sum2.out" , "w" , stdout); int l , r ; cin>> n >> t ; for(int i= 1; i <= n; i++){ cin>>q[i]; } cin>>t; for(int i =0 ; i < t; i++){ cin>> a >> l >> r; l++; if(a==1){ update(1 , r , l , 1 , n ); } else { cout<<get(1 , l , r , 1 , n ).first << ' ' <<get(1 , l , r , 1 , n ).second << nn ; } } } //Life is good //aza genius machine nomer1=sigma //Azamat