Pagini recente » Cod sursa (job #802715) | Rezultatele filtrării | Cod sursa (job #1807870)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("arbint.in");
ofstream out("arbint.out");
const int nMax = 100005;
const int sqrtnMax = 320;
const int mMax = 100005;
int n, m;
int v[nMax];
int maxInt[sqrtnMax];
int nr;
int lung;
void setMaxInt(int x)
{
maxInt[x] = 0;
int start = lung * (x - 1);
for(int j = 1; j <= lung && start + j <= n; ++j)
maxInt[x] = max(maxInt[x], v[start + j]);
}
void citire()
{
in >> n >> m;
for(int i = 1; i <= n; ++i)
in >> v[i];
lung = sqrt(n);
nr = ceil(1.0f * n / lung);
for(int i = 1; i <= nr; ++i)
setMaxInt(i);
}
inline int getInt(int pos)
{
return(ceil(1.0f * pos / lung));
}
int query(int a, int b)
{
int startintv, stopintv;
int ret = 0;
int intv = getInt(a);
startintv = intv + 1;
int stop = intv * lung;
for(int i = a; i <= stop; ++i)
ret = max(ret, v[i]);
intv = getInt(b);
stopintv = intv - 1;
stop = (intv - 1) * lung;
for(int i = b; i >= stop; --i)
ret = max(ret, v[i]);
for(int i = startintv; i <= stopintv; ++i)
ret = max(ret, maxInt[i]);
return ret;
}
void update(int a, int b)
{
int p = getInt(a);
if(v[a] == maxInt[p]) //ceva optimizare
{
v[a] = b;
setMaxInt(p);
}
else
{
maxInt[p] = max(maxInt[p], b);
v[a] = b;
}
}
int main()
{
citire();
int o, a, b;
for(int i = 1; i <= m; ++i)
{
in >> o >> a >> b;
if(o == 0)
out << query(a, b) << "\n";
else
update(a, b);
}
return 0;
}