Pagini recente » Cod sursa (job #57720) | Cod sursa (job #2533352) | Cod sursa (job #2726666) | Cod sursa (job #2084694) | Cod sursa (job #2720497)
#include <iostream>
#include <fstream>
#define NMAX 100000
using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");
int n, q, aint[4*NMAX+10], v[NMAX+10], k;
void init()
{ for(int i=n; i<n+k; i++)
aint[i] = v[i-n+1];
for(int i=n-1; i; i--)
aint[i] = max(aint[2*i], aint[2*i+1]);
}
void update(int poz, int val)
{ poz = poz + n - 1;
aint[poz] = val;
poz /= 2;
while(poz)
{ aint[poz] = max(aint[2*poz], aint[2*poz+1]);
poz /= 2;
}
}
int query(int nod, int stnod, int drnod, int stq, int drq)
{ if(stq <= stnod && drnod <= drq)
return aint[nod];
int mij = (stnod + drnod) / 2, ans = 0;
if(stq <= mij)
ans = max(ans, query(2*nod, stnod, mij, stq, drq));
if(drq > mij)
ans = max(ans, query(2*nod+1, mij+1, drnod, stq, drq));
return ans;
}
int main()
{
fin >> n >> q;
for(int i=1; i<=n; i++)
fin >> v[i];
k = n;
int bit = 0;
while((1 << bit) < n)
bit++;
n = (1 << bit);
init();
while(q--)
{ int type, a, b;
fin >> type >> a >> b;
if(!type)
fout << query(1, 1, n, a, b) << '\n';
else
update(a, b);
}
return 0;
}