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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define mp make_pair
#define l_bnd lower_bound

using namespace std;

int pocz[500005];
int zmiany[500005][2];
set <pair <int, int> > chg[500005];
int tem, ucz;

inline int war(int nrtem, int nrucz)
{
	return prev(chg[nrtem].l_bnd(mp(nrucz+1, -1)))->second;
}

inline void wypisz(int p, int k)
{
	for(int i=p; i<k; i++) printf("%d ", i+1);
}

const int hsize=1<<19;

int drz[hsize*2];
const int inf=100000000;

inline void updejt(int poz)
{
	drz[poz]=min(drz[poz*2], drz[poz*2+1]);
}

void updrz(int poz, int val)
{
	poz+=hsize;
	drz[poz]=val;
	while(poz>1)
	{
		poz>>=1;
		updejt(poz);
	}
}

int drzewo(int poc, int kon)
{
	int ret=inf;
	poc+=hsize;
	kon+=hsize;
	ret=min(ret, drz[poc]);
	if(poc!=kon) ret=min(ret, drz[kon]);
	while(poc+1<kon)
	{
		if((poc&1)==0) ret=min(ret, drz[poc+1]);
		if((kon&1)==1) ret=min(ret, drz[kon-1]);
		poc>>=1;
		kon>>=1;
	}
	return ret;
}

int rek(int poc, int kon)
{
	//cerr<<"rek "<<poc<<" "<<kon<<endl;
	if(poc>=kon) return 0;
	if(poc+1==kon) 
	{
		wypisz(poc, kon);
		return 0;
	}
	int mn=drzewo(poc, kon-1);
	if(mn==inf)
	{
		wypisz(poc, kon);
		return 0;
	}
	int poz=kon;
	vector <pair <int, pair <int, int> > > przed;
	while(poz>poc)
	{
		auto pop=*prev(chg[mn].l_bnd(mp(poz, -1)));
		int npoz=pop.first;
		int war=pop.second;
		przed.push_back(mp(war, mp(npoz, poz)));
		poz=npoz;
	}
	for(auto i:przed)
	{
		if(i.second.first>=poc) updrz(i.second.first, inf);
	}
	//for(int i=0; i<ucz; i++) cerr<<drzewo(i, i)<<" ";
	//cerr<<endl;
	sort(przed.begin(), przed.end());
	for(auto i:przed) rek(max(i.second.first, poc), i.second.second);
	return 0;
}

int main()
{
	scanf("%d%d", &tem, &ucz);
	for(int i=0; i<tem; i++) scanf("%d", &pocz[i]);
	for(int i=1; i<ucz; i++) scanf("%d%d", &zmiany[i][0], &zmiany[i][1]); //nr, war
	for(int i=1; i<ucz; i++) zmiany[i][0]--;
	for(int i=0; i<tem; i++) chg[i].insert(mp(-1, pocz[i])); 
	for(int i=1; i<ucz; i++) chg[zmiany[i][0]].insert(mp(i, zmiany[i][1]));
	updrz(0, inf);
	for(int i=1; i<ucz; i++) updrz(i, zmiany[i][0]);
	updrz(ucz, inf);
	rek(0, ucz);
	printf("\n");
}