#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 500500; const int K = 700; int n,m; int t[N], p[N], x[N]; vector<pii> chg[N]; pair<pii,int> val[N]; void merge(int pos, int npos) { /*printf("wejscie:\n"); FOR(jj,2) { printf("%d : ", t[pos+jj]); FOR(i,SZ(chg[pos+jj])) printf("(%d %d) ", chg[pos+jj][i].fi, chg[pos+jj][i].se); printf("\n"); }*/ pii cur = mp(t[pos], t[pos+1]); val[0] = mp(cur, 0); int i=0, j=0, q=1; while (i<SZ(chg[pos]) || j<SZ(chg[pos+1])) { if (i==SZ(chg[pos]) || (j<SZ(chg[pos+1]) && chg[pos+1][j].fi < chg[pos][i].fi)) { cur.se = chg[pos+1][j].se; val[q++] = mp(cur, chg[pos+1][j].fi); j++; } else { cur.fi = chg[pos][i].se; val[q++] = mp(cur, chg[pos][i].fi); i++; } } // todo: sort liniowo sort(val, val+q); t[pos] = t[pos+1] = 0; chg[pos].clear(); chg[pos+1].clear(); int rr=0; FOR(i,q) { if (i>0 && val[i].fi!=val[i-1].fi) rr++; if (val[i].se == 0) t[npos] = rr; else chg[npos].pb(mp(val[i].se, rr)); } // todo: sort liniowo sort(chg[npos].begin(), chg[npos].end()); /*printf("wyjscie:\n"); printf("%d : ", t[npos]); FOR(i,SZ(chg[npos])) printf("(%d %d) ", chg[npos][i].fi, chg[npos][i].se); printf("\n");*/ } vi allx; map<int,int> idx; int main() { scanf("%d%d", &n, &m); FOR(i,n) { scanf("%d", &t[i]); allx.pb(t[i]); } FORI(i,m-1) { scanf("%d%d", &p[i], &x[i]); p[i]--; allx.pb(x[i]); } sort(allx.begin(), allx.end()); FOR(i,SZ(allx)) idx[allx[i]] = i; FOR(i,n) t[i]=idx[t[i]]; FORI(i,m-1) { x[i] = idx[x[i]]; chg[p[i]].pb(mp(i, x[i])); } int siz = n; while (siz > 1) { for (int i = 0; i < n; i+=2) { merge(i, i/2); } siz = (siz+1) / 2; } FOR(i,SZ(chg[0])) swap(chg[0][i].fi, chg[0][i].se); chg[0].pb(mp(t[0],0)); sort(chg[0].begin(), chg[0].end()); FOR(i,SZ(chg[0])) printf("%d ", chg[0][i].se+1); printf("\n"); 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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 500500; const int K = 700; int n,m; int t[N], p[N], x[N]; vector<pii> chg[N]; pair<pii,int> val[N]; void merge(int pos, int npos) { /*printf("wejscie:\n"); FOR(jj,2) { printf("%d : ", t[pos+jj]); FOR(i,SZ(chg[pos+jj])) printf("(%d %d) ", chg[pos+jj][i].fi, chg[pos+jj][i].se); printf("\n"); }*/ pii cur = mp(t[pos], t[pos+1]); val[0] = mp(cur, 0); int i=0, j=0, q=1; while (i<SZ(chg[pos]) || j<SZ(chg[pos+1])) { if (i==SZ(chg[pos]) || (j<SZ(chg[pos+1]) && chg[pos+1][j].fi < chg[pos][i].fi)) { cur.se = chg[pos+1][j].se; val[q++] = mp(cur, chg[pos+1][j].fi); j++; } else { cur.fi = chg[pos][i].se; val[q++] = mp(cur, chg[pos][i].fi); i++; } } // todo: sort liniowo sort(val, val+q); t[pos] = t[pos+1] = 0; chg[pos].clear(); chg[pos+1].clear(); int rr=0; FOR(i,q) { if (i>0 && val[i].fi!=val[i-1].fi) rr++; if (val[i].se == 0) t[npos] = rr; else chg[npos].pb(mp(val[i].se, rr)); } // todo: sort liniowo sort(chg[npos].begin(), chg[npos].end()); /*printf("wyjscie:\n"); printf("%d : ", t[npos]); FOR(i,SZ(chg[npos])) printf("(%d %d) ", chg[npos][i].fi, chg[npos][i].se); printf("\n");*/ } vi allx; map<int,int> idx; int main() { scanf("%d%d", &n, &m); FOR(i,n) { scanf("%d", &t[i]); allx.pb(t[i]); } FORI(i,m-1) { scanf("%d%d", &p[i], &x[i]); p[i]--; allx.pb(x[i]); } sort(allx.begin(), allx.end()); FOR(i,SZ(allx)) idx[allx[i]] = i; FOR(i,n) t[i]=idx[t[i]]; FORI(i,m-1) { x[i] = idx[x[i]]; chg[p[i]].pb(mp(i, x[i])); } int siz = n; while (siz > 1) { for (int i = 0; i < n; i+=2) { merge(i, i/2); } siz = (siz+1) / 2; } FOR(i,SZ(chg[0])) swap(chg[0][i].fi, chg[0][i].se); chg[0].pb(mp(t[0],0)); sort(chg[0].begin(), chg[0].end()); FOR(i,SZ(chg[0])) printf("%d ", chg[0][i].se+1); printf("\n"); return 0; } |