631C - Report - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define int long long
#define ar array<int, 2>
#define arr array<int, 3>
const int N = 2e5 + 5, M = 2 * N;
const int inf = 0x3f3f3f3f3f3f3f3f;
int mod = 998244353; //1e9+7;
int t, n, m, k;
ar st[N];
signed main()
{
    ios;
#ifdef DEBUG
    freopen("../1.in", "r", stdin);
#endif
    // 这题还是可以刷的。
    // 就是实现技巧如果好的话。。会很舒服。。
    // 虽然我自己做出来的哈哈哈。。
    cin >> n >> m;
    int a[n + 1], b[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> a[i], b[i] = a[i];
    int l = 0;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        while (l && st[l][1] <= y)
            l--;
        st[++l] = {x, y};
    }
    sort(a + 1, a + st[1][1] + 1);
    int x = 1, y = st[1][1];
    st[l + 1][1] = 0; //这个很细节。l在进退的时候 这个位置是有可能被污染过的。
    // 后面我们要用到。。所以要给他稳定的重置为0
    for (int i = 1; i <= l; ++i)
    {
        auto &[u, v] = st[i];
        for (int j = v; j > st[i + 1][1]; j--)
            if (u == 1)
                b[j] = a[y--];
            else
                b[j] = a[x++];
    }
    for (int i = 1; i <= n; ++i)
        cout << b[i] << " ";
};