Pagini recente » Cod sursa (job #1197226) | Cod sursa (job #2069026) | Cod sursa (job #1296622) | Cod sursa (job #1612029) | Cod sursa (job #2263036)
#include<iostream>
#include<vector>
#include<cstdio>
#define ERR -2018
#define INT_MIN -1.e+9
using namespace std;
class SegNode{
public:
int l,u;//lower and upper limit
SegNode* left;
SegNode* right;
int val;
SegNode(int L , int U , vector<int>* arr) {
if(L<=U){
l = L;
u = U;
if(u==l){
val = (*arr)[u];
left = right = 0;
}
else{
int h = (l+u)/2;
left = new SegNode(l , h, arr);
right = new SegNode(h+1 , u, arr);
val = max(left->val , right->val);
}
}
}
//return true if [x,y] overlaps [l,u]
bool overlaps(int x,int y){
int a=l , b=u;
return ((a<=x) && (x<=b)) || ((a<=y) && (y<=b)) ||
((x<=a) && (a<=y)) || ((x<=b) && (b<=y));
}
int search_max(int a, int b)//get maximum value between indexes a and b
{
//if((a<0) || (b>N) || (a>b)) return ERR;
if(!this->overlaps(a,b))
return INT_MIN;
if(a<=l && u<=b) //if [l,u] included in [a,b]
return val;
return max(left->search_max(a,b) , right->search_max(a,b));
}
void update_value(int k,int v)//arr[k]=v
{
if(l==u){
if(l==k) val = v;
return;
}
//else
int h = (l+u)/2;
if(k<=h)
left->update_value(k,v);
else
right->update_value(k,v);
val = max(left->val , right->val);
}
void destroy()
{
if(left) left->destroy();
delete left;
if(right) right->destroy();
delete right;
}
void print()
{
printf("[%d,%d] ",l,u);
if(left) (*left).print();
if(right) (*right).print();
}
};
class SegTree{
SegNode* root;
int N;//interval size
public:
SegTree(vector<int>* arr)
{
N = arr->size()-1;
root = new SegNode(0,N,arr);
}
void update_value(int k,int v)//arr[k]=v
{
root->update_value(k,v);
}
int search_max(int a, int b)//get maximum value between indexes a and b
{
if((a<0) || (b>N) || (a>b)) return ERR;
return root->search_max(a,b);
}
void print()
{
root->print();
}
void destroy(){
root->destroy();
}
};
int main()
{
freopen("arbint.in","r",stdin);
freopen("arbint.out","w",stdout);
int N,M;
cin>>N>>M;
vector<int> arr(N);
for(int i=0;i<N;i++)
cin>>arr[i];
SegTree tree(&arr);
int op,a,b;
while(M--){
cin>>op>>a>>b;
if(op) //update
tree.update_value(a-1,b);
else //get max
cout<<tree.search_max(a-1,b-1)<<"\n";
}
return 0;
}