Untitled
unknown
plain_text
2 years ago
3.8 kB
11
Indexable
#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] << " "; } }
Editor is loading...