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
#include <cstdio>
#include <cstdlib>
#include <cassert>

#include <algorithm>
#include <set>
#include <vector>

static const int MAX_N = 500 * 1000;
static const int MAX_M = 500 * 1000;

static const int TREE_BASE = 512 * 1024;

struct change_t {
	int pupil;
	int position;
	int value;
};

struct tree_t {
	int position;
	int diff;
};

int original_sequence[MAX_N];
change_t changes[MAX_M];
tree_t tree[2 * TREE_BASE];

int n, m;

void read_data() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", original_sequence + i);
	}

	for (int i = 0; i < m - 1; i++) {
		changes[i].pupil = i + 1;
		scanf("%d %d", &changes[i].position, &changes[i].value);
		changes[i].position--;
	}
}

bool compare_changes(const change_t & a, const change_t & b) {
	if (a.position != b.position) {
		return a.position < b.position;
	}
	return a.pupil < b.pupil;
}

bool compare_pupils(int a, int b) {
	int i = 0;
	while (i < m - 1) {
		int j = i;
		while (j < m - 1 && changes[i].position == changes[j].position) {
			j++;
		}

		int afield = original_sequence[changes[i].position];
		int bfield = afield;
		for (int k = i; k < j; k++) {
			if (changes[k].pupil <= a) {
				afield = changes[k].value;
			}
			if (changes[k].pupil <= b) {
				bfield = changes[k].value;
			}
		}

		if (afield != bfield) {
			return afield < bfield;
		}

		i = j;
	}

	return a < b;
}

int main() {
	read_data();
	std::sort(changes, changes + (m - 1), compare_changes);

	std::vector<int> pupils;
	for (int i = 0; i < m; i++) {
		pupils.push_back(i);
	}
	std::sort(pupils.begin(), pupils.end(), compare_pupils);

	bool first = true;
	for (int p : pupils) {
		if (first) {
			printf("%d", p + 1);
			first = false;
		}
		else {
			printf(" %d", p + 1);
		}
	}
	puts("");

	return 0;
}