# Untitled

unknown
plain_text
7 months ago
3.8 kB
7
Indexable
Never
```#include <iostream>

int n, q;
using namespace std;
int MinI;
int MaxI;
int l, r;

void BuildMin(int *A, pair<int, int> a[], int v, int Al, int Ar) {
if (Al == Ar) {
a[v].first = A[Al];
}
else {
int Am = (Al + Ar) / 2;
BuildMin(A, a, v * 2, Al, Am);
BuildMin(A, a, v * 2 + 1, Am + 1, Ar);
a[v] = make_pair(min(a[v * 2 + 1].first, a[v * 2].first),v);
}
}

void BuildMax(int* A, pair<int, int> a[], int v, int Al, int Ar) {
if (Al == Ar) {
a[v].first = A[Al];
}
else {
int Am = (Al + Ar) / 2;
BuildMax(A, a, v * 2, Al, Am);
BuildMax(A, a, v * 2 + 1, Am + 1, Ar);
a[v] = make_pair(max(a[v * 2 + 1].first, a[v * 2].first), v);

}
}

pair<int, int> Min(pair<int,int> *t,int v, int tl, int tr, int l, int r) {
if (l > r) {
return make_pair((int)100000, (int)0);
}
if (tl == l && tr == r) {
return t[v];
}
int tm = (tr - tl) / 2;
pair<int, int> x1 = Min(t, v * 2, tl, tm, l, min(r, tm));
pair<int, int> x2 = Min(t, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
if (x1.first < x2.first) {
return x1;
}
else {
return x2;
}
}

pair<int, int> Max(pair<int, int>* t, int v, int tl, int tr, int l, int r) {
if (l > r) {
return make_pair((int)0, (int)0);
}
if (tl == l && tr == r) {
return t[v];
}
int tm = (tr - tl) / 2;
pair<int, int> x1 = Max(t, v * 2, tl, tm, l, min(r, tm));
pair<int, int> x2 = Max(t, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
if (x1.first > x2.first) {
return x1;
}
else {
return x2;
}
}

void updateMin(pair<int,int> *t, int v, int tl, int tr, int pos, int new_val) {
if (tl == tr)
t[v].first = new_val;
else {
int tm = (tl + tr) / 2;
if (pos <= tm)
updateMin(t, v * 2, tl, tm, pos, new_val);
else
updateMin(t, v * 2 + 1, tm + 1, tr, pos, new_val);
if (t[v * 2].first < t[v * 2 + 1].first) {
forward < pair<int, int>>(t[v]) = t[v * 2];
}
else {
forward < pair<int, int>>(t[v]) = t[v * 2 + 1];
}
}
}

void updateMax(pair<int, int>* t, int v, int tl, int tr, int pos, int new_val) {
if (tl == tr)
t[v].first = new_val;
else {
int tm = (tl + tr) / 2;
if (pos <= tm)
updateMax(t, v * 2, tl, tm, pos, new_val);
else
updateMax(t, v * 2 + 1, tm + 1, tr, pos, new_val);
if (t[v * 2].first > t[v * 2 + 1].first) {
forward<pair<int, int>>(t[v]) = t[v * 2];
}
else {
forward < pair<int, int>>(t[v]) = t[v * 2 + 1];
}
}
}

int main()
{
cin >> n >> q;
int* A = new int[n];
pair<int,int>* tmin = new pair<int,int>[4 * n];
pair<int, int>* tmax = new pair<int, int>[4 * n];

for (int i = 0; i < n; ++i) {
cin >> A[i];
}

BuildMin(A, tmin, 1, 0, n - 1);
BuildMax(A, tmax, 1, 0, n - 1);

for (int i = 0; i < q; ++i) {
cin >> l >> r;

pair<int, int> qmin = Min(tmin, 1, 0, n - 1, l, r);
pair<int, int> qmax = Max(tmax, 1, 0, n - 1, l, r);
updateMin(tmin, 1, 0, n - 1, qmin.second, qmax.first);
updateMax(tmax, 1, 0, n - 1, qmin.second, qmax.first);
updateMin(tmin, 1, 0, n - 1, qmax.second, qmin.first);
updateMax(tmax, 1, 0, n - 1, qmax.second, qmin.first);
A[qmin.second] = qmax.first;
A[qmax.second] = qmin.first;
}
for (int i = 0; i < n; ++i) {
cout << A[i] << " ";
}
}```