Pagini recente » Cod sursa (job #27768) | Rezultatele filtrării | Cod sursa (job #467620) | Rezultatele filtrării | Cod sursa (job #2677738)
#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)
{
v[ind] = val;
int maxii = -1;
int kezd = (ind - 1) / gyok * gyok + 1;
int veg = ((ind - 1) / gyok + 1) * gyok;
for (int i = kezd; i <= veg; ++i)
if(v[i]>maxii) maxii = v[i];
maxi[(ind - 1) / gyok + 1] = maxii;
}
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;
}