#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head inline int getint() { int ret=0;bool ok=0; for(;;) { int c=getchar(); if(c>='0'&&c<='9')ret=(ret<<3)+ret+ret+c-'0',ok=1; else if(ok)return ret; } } const int N=12000000,M=501000; int rk[N],pl[N],pr[N],pre[N],cur; int rt[M],nd[M],a[M],p1[M],p2[M],buf[M],ret[M],vl[M],vr[M]; int n,m; int build(int l,int r) { int c=++cur; if (l==r) { rk[c]=a[l]; } else { int md=(l+r)>>1; pl[c]=build(l,md); pr[c]=build(md+1,r); } return c; } int modify(int p,int l,int r,int x,int v) { int c=++cur; pre[c]=p; pl[c]=pl[p]; pr[c]=pr[p]; if (l==r) rk[c]=v; else { int md=(l+r)>>1; if (x<=md) pl[c]=modify(pl[p],l,md,x,v); else pr[c]=modify(pr[p],md+1,r,x,v); } return c; } int solve(int p,int l,int r) { if (l==r) { int u=p,cnt=0; while (u) { nd[cnt++]=u; u=pre[u]; } sort(nd,nd+cnt,[&](int a,int b) { return rk[a]<rk[b]; }); int tot=0; rep(i,0,cnt) { int v=rk[nd[i]]; rk[nd[i]]=tot; if (i!=cnt-1&&v!=rk[nd[i+1]]) tot++; } return tot+1; } else { int md=(l+r)>>1; int ls=solve(pl[p],l,md); int rs=solve(pr[p],md+1,r); int u=p,cnt=0; while (u) { nd[cnt]=u; vl[cnt]=rk[pl[u]]; vr[cnt]=rk[pr[u]]; ++cnt; u=pre[u]; } rep(i,0,rs) buf[i]=0; rep(i,0,cnt) buf[vr[i]]++; rep(i,1,rs) buf[i]+=buf[i-1]; per(i,0,cnt) p1[--buf[vr[i]]]=i; rep(i,0,ls) buf[i]=0; rep(i,0,cnt) buf[vl[p1[i]]]++; rep(i,1,ls) buf[i]+=buf[i-1]; per(i,0,cnt) p2[--buf[vl[p1[i]]]]=p1[i]; int tot=0; rep(i,0,cnt) { if (i!=0&&(vl[p2[i]]!=vl[p2[i-1]]||vr[p2[i]]!=vr[p2[i-1]])) tot++; rk[nd[p2[i]]]=tot; } return tot+1; } } int main() { n=getint(); m=getint(); rep(i,1,n+1) a[i]=getint(); rt[1]=build(1,n); rep(i,2,m+1) { int t=getint(),v=getint(); rt[i]=modify(rt[i-1],1,n,t,v); } solve(rt[m],1,n); rep(i,1,m+1) ret[i]=i; sort(ret+1,ret+m+1,[&](int a,int b) { return rk[rt[a]]==rk[rt[b]]?a<b:rk[rt[a]]<rk[rt[b]]; }); rep(i,1,m+1) printf("%d%c",ret[i]," \n"[i==m]); }
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 | #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head inline int getint() { int ret=0;bool ok=0; for(;;) { int c=getchar(); if(c>='0'&&c<='9')ret=(ret<<3)+ret+ret+c-'0',ok=1; else if(ok)return ret; } } const int N=12000000,M=501000; int rk[N],pl[N],pr[N],pre[N],cur; int rt[M],nd[M],a[M],p1[M],p2[M],buf[M],ret[M],vl[M],vr[M]; int n,m; int build(int l,int r) { int c=++cur; if (l==r) { rk[c]=a[l]; } else { int md=(l+r)>>1; pl[c]=build(l,md); pr[c]=build(md+1,r); } return c; } int modify(int p,int l,int r,int x,int v) { int c=++cur; pre[c]=p; pl[c]=pl[p]; pr[c]=pr[p]; if (l==r) rk[c]=v; else { int md=(l+r)>>1; if (x<=md) pl[c]=modify(pl[p],l,md,x,v); else pr[c]=modify(pr[p],md+1,r,x,v); } return c; } int solve(int p,int l,int r) { if (l==r) { int u=p,cnt=0; while (u) { nd[cnt++]=u; u=pre[u]; } sort(nd,nd+cnt,[&](int a,int b) { return rk[a]<rk[b]; }); int tot=0; rep(i,0,cnt) { int v=rk[nd[i]]; rk[nd[i]]=tot; if (i!=cnt-1&&v!=rk[nd[i+1]]) tot++; } return tot+1; } else { int md=(l+r)>>1; int ls=solve(pl[p],l,md); int rs=solve(pr[p],md+1,r); int u=p,cnt=0; while (u) { nd[cnt]=u; vl[cnt]=rk[pl[u]]; vr[cnt]=rk[pr[u]]; ++cnt; u=pre[u]; } rep(i,0,rs) buf[i]=0; rep(i,0,cnt) buf[vr[i]]++; rep(i,1,rs) buf[i]+=buf[i-1]; per(i,0,cnt) p1[--buf[vr[i]]]=i; rep(i,0,ls) buf[i]=0; rep(i,0,cnt) buf[vl[p1[i]]]++; rep(i,1,ls) buf[i]+=buf[i-1]; per(i,0,cnt) p2[--buf[vl[p1[i]]]]=p1[i]; int tot=0; rep(i,0,cnt) { if (i!=0&&(vl[p2[i]]!=vl[p2[i-1]]||vr[p2[i]]!=vr[p2[i-1]])) tot++; rk[nd[p2[i]]]=tot; } return tot+1; } } int main() { n=getint(); m=getint(); rep(i,1,n+1) a[i]=getint(); rt[1]=build(1,n); rep(i,2,m+1) { int t=getint(),v=getint(); rt[i]=modify(rt[i-1],1,n,t,v); } solve(rt[m],1,n); rep(i,1,m+1) ret[i]=i; sort(ret+1,ret+m+1,[&](int a,int b) { return rk[rt[a]]==rk[rt[b]]?a<b:rk[rt[a]]<rk[rt[b]]; }); rep(i,1,m+1) printf("%d%c",ret[i]," \n"[i==m]); } |