Untitled

#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] << " ";
    }
}