Pagini recente » Borderou de evaluare (job #919848) | Diferente pentru newsletter/algoritmiada-2014-runda-finala intre reviziile 2 si 8 | Borderou de evaluare (job #818460) | Cod sursa (job #1186365) | Cod sursa (job #2677744)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("arbint.in");
ofstream cout("arbint.out");
int n, m, t, x, y, gyok;
vector<int>v,maxi;
void Update(int ind, int val)
{
int hol = (ind - 1) / gyok + 1;
if (val >= maxi[hol])
{
v[ind] = val;
maxi[hol] = val;
}
else if (v[ind] == maxi[hol])
{
v[ind] = val;
int maxii = -1;
int kezd = (hol - 1) * gyok + 1;
int veg = hol * gyok;
for (int i = kezd; i <= veg; ++i)
if (v[i] > maxii) maxii = v[i];
maxi[hol] = maxii;
}
else v[ind] = val;
}
long long Query(int l, int r)
{
int akt_max = -1;
while (l <= r && l % gyok != 1)
{
if (v[l] > akt_max) akt_max = v[l];
++l;
}
while (r >= l && r % gyok != 0)
{
if (v[r] > akt_max) akt_max = v[r];
--r;
}
int k = (l - 1) / gyok + 1;
int v = (r - 1) / gyok + 1;
if (l <= r)
for (int i = k; i <= v; ++i)
if (maxi[i] > akt_max) akt_max = maxi[i];
return akt_max;
}
int main()
{
cin >> n >> m;
gyok = sqrt(n);
v.resize(n + 1, 0);
maxi.resize((n - 1) / gyok + 2, -1);
int k = 0;
for (int i = 1; i <= n; ++i)
{
cin >> v[i];
k = (i - 1) / gyok + 1;
if (v[i] > maxi[k]) maxi[k] = v[i];
}
while (m)
{
--m;
cin >> t >> x >> y;
if (t == 1) Update(x, y);
else cout << Query(x, y) << "\n";
}
return 0;
}