Original link: https://www.shuizilong.com/house/archives/luogu-3369/
#include <lastweapon/io> using namespace lastweapon; namespace SBT { const static int N = int(1e5) + 9; int c[2][N], sz[N], ky[N], tot; #define lc[d] #define rc[!d] #define lx l[x] #define rx r[x] #define kx ky[x] #define sx sz[x] #define d 0 int new_node(int v = 0){ int x=tot++;lx=rx=0; sx=1;kx=v; return x; } void upd(int x){ sx=sz[lx]+1+sz[rx]; } #undef d void rot(int &x,int d){ int y=rx;rx=l[y];l[y]=x; upd(x),upd(y),x=y; } void fix(int &x,int d){ if (sz[l[lx]] > sz[rx]) rot(x,!d); else{ if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d); else return; } d=0,fix(lx,0),fix(rx,1); fix(x,0),fix(x,1); } #define d 0 void Ins(int &x,int v){ if(!x) x = new_node(v); else{ ++sz[x]; Ins(c[v>kx][x],v); fix(x,v>kx); } } int d_key; void Del(int &x,int v){ --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){ if(!lx||!rx) d_key = kx, x = lx | rx; else Del(lx,v+1), kx = d_key; } else Del(c[v>kx][x],v); } int Rank(int x,int v) { if (!x) return 0; return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v); } int Select(int x,int k) { if (k == sz[lx]) return kx; return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1); } int upper(int x, int k) { int z; while (x) { if (kx > k) z = x, x = lx; else x = rx; } return ky[z]; } int lower(int x,int k) { int z; while (x) { if (kx < k) z = x, x = rx; else x = lx; } return ky[z]; } #undef d #undef sx #undef kx #undef lx #undef rx #undef l #undef r } using namespace SBT; int rt; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif tot = 1; int cmd, x; Rush { int cmd; RD(cmd); RD(x); //cout << cmd << " " << x << endl; switch(cmd) { case 1: Ins(rt, x); break; case 2: Del(rt, x); break; case 3: OT(Rank(rt, x)+1); break; case 4: OT(Select(rt, x-1)); break; case 5: //OT(lower(rt, x)); OT(Select(rt, Rank(rt, x)-1)); break; case 6: //OT(upper(rt, x)); OT(Select(rt, Rank(rt, x+1))); break; } } }
#include <lastweapon/io> using namespace lastweapon; namespace Scapegoat_Tree { const static int N = int(1e5) + 9; const static DB alpha = 0.7; int c[2][N], sz[N], ky[N], tot; #define lc[d] #define rc[!d] #define lx l[x] #define rx r[x] #define kx ky[x] #define sx sz[x] #define d 0 int new_node(int v = 0){ int x=tot++;lx=rx=0; sx=1;kx=v; return x; } void upd(int x){ sx=sz[lx]+1+sz[rx]; } bool bad(int x) { return max(sz[lx], sz[rx]) >= int(sx * alpha); } void build(int &x, int ll, int rr, VI& T) { if (ll >= rr) x = 0; else { int ml = (ll+rr) >> 1, mr = ml + 1; x = T[ml]; build(lx, ll, ml, T); build(rx, mr, rr, T); upd(x); } } void collect(int x, VI& T) { if (!x) return; collect(lx, T); T.PB(x); collect(rx, T); } void rebuild(int& x) { VI T; collect(x, T); build(x, 0, SZ(T), T); } void Ins(int &x,int v){ if(!x) x = new_node(v); else{ ++sz[x]; Ins(c[v>kx][x],v); if (bad(x)) rebuild(x); } } int d_key; void Del(int &x,int v){ --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){ if(!lx||!rx) d_key = kx, x = lx | rx; else Del(lx,v+1), kx = d_key; } else Del(c[v>kx][x],v); } int Rank(int x,int v) { if (!x) return 0; return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v); } int Select(int x,int k) { if (k == sz[lx]) return kx; return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1); } int upper(int x, int k) { int z; while (x) { if (kx > k) z = x, x = lx; else x = rx; } return ky[z]; } int lower(int x,int k) { int z; while (x) { if (kx < k) z = x, x = rx; else x = lx; } return ky[z]; } void inorder(int x) { if (!x) return; inorder(lx); printf("%d ", ky[x]); inorder(rx); } #undef d #undef sx #undef kx #undef lx #undef rx #undef l #undef r } using namespace Scapegoat_Tree; int rt; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif tot = 1; int cmd, x; Rush { int cmd; RD(cmd); RD(x); switch(cmd) { case 1: Ins(rt, x); break; case 2: Del(rt, x); break; case 3: OT(Rank(rt, x)+1); break; case 4: OT(Select(rt, x-1)); break; case 5: OT(lower(rt, x)); //OT(Select(rt, Rank(rt, x)-1)); break; case 6: OT(upper(rt, x)); //OT(Select(rt, Rank(rt, x+1))); break; } } }
This article is reprinted from: https://www.shuizilong.com/house/archives/luogu-3369/
This site is for inclusion only, and the copyright belongs to the original author.