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
#include<cstdio>
#include<algorithm>
typedef unsigned long long ll;
const int N=500010,M=12000000,BUF=20000000;
char Buf[BUF],*buf=Buf;
int n,m,i,x,y,s[N],T[N],q[N],tot,l[M],r[M];ll v[M];
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline void up(int x){v[x]=(((v[l[x]]+17)*233)^19971123)+v[r[x]];}
int build(int a,int b){
  int x=++tot;
  if(a==b){
    v[x]=s[a];
    return x;
  }
  int mid=(a+b)>>1;
  l[x]=build(a,mid);
  r[x]=build(mid+1,b);
  up(x);
  return x;
}
int change(int x,int a,int b,int c,int d){
  int y=++tot;
  if(a==b){
    v[y]=d;
    return y;
  }
  int mid=(a+b)>>1;
  if(c<=mid)l[y]=change(l[x],a,mid,c,d),r[y]=r[x];
  else l[y]=l[x],r[y]=change(r[x],mid+1,b,c,d);
  up(y);
  return y;
}
bool check(int x,int y,int a,int b){
  if(v[x]==v[y])return 0;
  if(a==b)return v[x]<v[y];
  int mid=(a+b)>>1;
  if(v[l[x]]==v[l[y]])return check(r[x],r[y],mid+1,b);
  return check(l[x],l[y],a,mid);
}
inline bool cmp(int x,int y){return check(T[x],T[y],1,n);}
int main(){
  fread(Buf,1,BUF,stdin);read(n),read(m);
  for(i=1;i<=n;i++)read(s[i]);
  T[1]=build(1,n);
  for(i=2;i<=m;i++)read(x),read(y),T[i]=change(T[i-1],1,n,x,y);
  for(i=1;i<=m;i++)q[i]=i;
  std::sort(q+1,q+m+1,cmp);
  for(i=1;i<=m;i++)printf("%d ",q[i]);
}