1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;

typedef vector<pair<pair<int, int>, int> > Result;

const int N = 500005;

int n, m;
int tab[N];
vector<pair<int, int > > changes[N];

Result solveForOne(int pos) {
    vector<pair<int, pair<int, int> > > intervals;
    int currentValue = tab[pos];
    int from = 1;
    for (int i = 0; i < changes[pos].size(); i++) {
        int to = changes[pos][i].first - 1;
        intervals.push_back({currentValue, {from, to}});
        currentValue = changes[pos][i].second;
        from = to + 1;
    }
    intervals.push_back({currentValue, {from, m}});
    sort(intervals.begin(), intervals.end());
    
    Result ret;
    int g = 0;
    for (int i = 0; i < intervals.size(); i++) {
        if (i == 0 || intervals[i].first != intervals[i - 1].first) {
            g++;
        }
        ret.push_back({intervals[i].second, g});
    }
    sort(ret.begin(), ret.end());
    return ret;
}

bool cmp(const pair<pair<int, int>, vector<pair<int, int> > > &a, pair<pair<int, int>, vector<pair<int, int> > > &b) {
    if (a.first == b.first) {
        return a.second[0].first < b.second[0].first;
    }
    return a.first < b.first;
}

Result merge(Result &leftResult, const Result &rightResult) {
    vector<pair<pair<int, int>, pair<int, int> > > newGroups;
    int ptr = 0;
    for (int i = 0; i < leftResult.size(); i++) {
        auto &elem = leftResult[i];
        pair<int, int> interval = elem.first;
        int myGroup = elem.second;
        while (ptr < rightResult.size() && rightResult[ptr].first.second < interval.first) {
            ptr++;
        }
        pair<pair<int, int>, int> whichGroup = rightResult[ptr];
        if (whichGroup.first.second < interval.second) {
            newGroups.push_back({{myGroup, whichGroup.second}, {interval.first, whichGroup.first.second}});
            elem.first.first = whichGroup.first.second + 1;
            i--;
        } else {
            newGroups.push_back({{myGroup, whichGroup.second}, {interval.first, interval.second}});
        }
    }
    sort(newGroups.begin(), newGroups.end());
    int g = 0;
    Result ret;
    for (int i = 0; i < newGroups.size(); i++) {
        if (i == 0 || newGroups[i].first != newGroups[i - 1].first) {
            g++;
        }
        ret.push_back({newGroups[i].second, g});
    }
    sort(ret.begin(), ret.end());
    return ret;
}

Result solve(int from, int to) {
    if (from == to) {
        return solveForOne(from);
    }
    int mid = (from + to) / 2;
    Result leftResult = solve(from, mid);
    Result rightResult = solve(mid + 1, to);
    return merge(leftResult, rightResult);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tab[i]);
    }
    
    for (int i = 2; i <= m; i++) {
        int pos, value;
        scanf("%d %d", &pos, &value);
        if ((changes[pos].empty() && tab[pos] == value) || (!changes[pos].empty() && changes[pos].back().second == value)) {
            continue;
        }
        changes[pos].push_back({i, value});
    }
    
    Result result = solve(1, n);
    vector<pair<int, pair<int, int> > > vec;
    for (const auto &x : result) {
        vec.push_back({x.second, x.first});
    }
    sort(vec.begin(), vec.end());
    for (const auto &interval : vec) {
        for (int i = interval.second.first; i <= interval.second.second; i++) {
            printf("%d ", i);
        }
    }
    
    return 0;
}