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