Cod sursa(job #2746736)

Utilizator Data 28 aprilie 2021 13:15:27 Arbori de intervale 100 cpp-64 done Arhiva educationala 1.8 kb
``````#include <bits/stdc++.h>

using namespace std;

typedef int(*Merge)(int, int);

class Aint{
public:
Aint(int size, Merge m): merge{m}{
arb.resize(4*size+4);
}
void update(int st, int dr, int poz, int actual_poz, int val){
if(st > actual_poz || dr < actual_poz) return;
if(st == dr){
arb[poz] = merge(arb[poz], val);
return;
}
int mid = (st+dr)/2;
update(st, mid, poz*2, actual_poz, val);
update(mid+1, dr, poz*2+1, actual_poz, val);
arb[poz] = merge(arb[poz*2], arb[poz*2+1]);
}
void insert(int st, int dr, int poz, int actual_poz, int val){
if(st > actual_poz || dr < actual_poz) return;
if(st == dr){
arb[poz] = val;
return;
}
int mid = (st+dr)/2;
insert(st, mid, poz*2, actual_poz, val);
insert(mid+1, dr, poz*2+1, actual_poz, val);
arb[poz] = merge(arb[poz*2], arb[poz*2+1]);
}
int get(int st, int dr, int poz, int a, int b){
// may change it to work with merge;
if(st > b || dr < a) return 0;
if(st >= a && dr <= b) return arb[poz];
int mid = (st+dr)/2;
return merge(get(st, mid, 2*poz, a, b), get(mid+1, dr, 2*poz+1, a, b));
}
vector<int> arb;
Merge merge;
};

int main(){
ifstream in("arbint.in");
ofstream out("arbint.out");
int n, m;
in >> n >> m;
Aint arb(n+1, [](int st, int dr){ return max(st, dr); });
for(int i=1; i<=n; i++){
int x;
in >> x;
arb.insert(1,n,1,i,x);
}
for(int i=1; i<=m; i++){
int c,a,b;
in >> c >> a >> b;
if(c){
arb.insert(1,n,1,a,b);
}
else{
out << arb.get(1,n,1,a,b) << '\n';
}
}
in.close();
out.close();
return 0;
}
``````