bzoj1056: [HAOI2008]排名系统
const int N = 1000010, MOD = 999997;struct Node {char Name[14];int No;} Tr[N];LL val[N];int Fa[N], C[N][2], Sz[N], No[N];int Root, n, Tot, Ans[N];int q[N], Top, Cache;int Fir[N], Nex[N], To[N], hnt, Cnt;inline void Write(int x) {if(!x) return;Write(C[x][1]);printf("%s ", Tr[No[x]].Name+1);Write(C[x][0]);}inline void UpDat(int x) {if(!x) return;Sz[x] = Sz[C[x][0]] + Sz[C[x][1]] + 1;}inline void rotate(int x, int c) {int y = Fa[x];Fa[x] = Fa[y], C[Fa[y]][C[Fa[y]][1] == y] = x;Fa[C[x][!c]] = y, C[y][c] = C[x][!c];Fa[y] = x, C[x][!c] = y;UpDat(y);}inline void Splay(int x, int g) {while(Fa[x] ^ g) {int y = Fa[x];int cy = C[Fa[y]][1] == y, cx = C[y][1] == x;if(Fa[y] == g) rotate(x, cx);else (cx == cy ? rotate(y, cy) : rotate(x, cx)), rotate(x, cy);}UpDat(x);if(!g) Root=x;}inline int Max(int x) {while(C[x][1]) x = C[x][1];return x;}inline int Min(int x) {while(C[x][0]) x = C[x][0];return x;}inline int Num() {if(Top) return q[Top--];return ++Cache;}inline void Ins(int y, int &x, LL sp, int po) {Tr[po].No = x = Num();Fa[x] = y, val[x] = sp, No[x] = po, Sz[x] = 1, C[x][0] = C[x][1] = 0;}inline void Del(int sp) {Splay(sp, 0);int x = Max(C[sp][0]), y = Min(C[sp][1]);Splay(x, 0), Splay(y, x), q[++Top] = C[y][0];Fa[C[y][0]] = 0, C[y][0] = 0;UpDat(y), UpDat(x);}inline int Rank(int rk) {int x = Root;while(x) {if(rk == Sz[C[x][0]]) break;else if(rk < Sz[C[x][0]]) x = C[x][0];else rk -= Sz[C[x][0]]+1, x = C[x][1];}return x;}inline int Hash(char *s) {int rt = 0;int len = strlen(s + 1);For(i, 1, len) rt = (rt * 27 + (s[i] - 'A' + 1)) % MOD;return rt;}inline int Pos(int z, char *s) {for(int i = Fir[z]; ~i; i = Nex[i])if(strcmp(s+1, Tr[To[i]].Name+1) == 0) return To[i];return -1;}inline void insert(int po, LL sp) {int x = Root;while(C[x][sp > val[x]]) x = C[x][sp > val[x]];Ins(x, C[x][sp > val[x]], sp, po);Splay(C[x][sp > val[x]], 0);}inline void INSERT(char *s, LL sp) {int z = Hash(s);int p = Pos(z, s);if(p == -1) {++hnt, To[Cnt] = hnt, Nex[Cnt] = Fir[z], Fir[z] = Cnt++;Ford(i, strlen(s + 1) + 1, 1) Tr[hnt].Name[i] = s[i];insert(hnt, sp);} else Del(Tr[p].No), insert(p, sp);}inline void dfs(int x) {if(!x) return;dfs(C[x][1]), Ans[++Tot] = No[x], dfs(C[x][0]);}inline void QUERY(int ed) {ed = Sz[Root] - 2 - ed + 1;int st = max(ed - 9, 1);int x = Rank(st - 1), y = Rank(ed + 1);Splay(x, 0), Splay(y, x), Tot = 0, dfs(C[y][0]);For(i, 1, Tot - 1) printf("%s ", Tr[Ans[i]].Name+1);printf("%s\n", Tr[Ans[Tot]].Name+1);}inline void QUERY(char *s) {int z = Hash(s);int p = Pos(z, s);Splay(Tr[p].No, 0);printf("%d\n", Sz[C[Tr[p].No][1]]);}inline void Solve() {char str[49], s[49];LL Dat;int LDat;clr(Fir, -1), Cnt = 0;Ins(Cache = 0, Root, -MLL, 0), Ins(Root, C[Root][1], MLL, 0), Sz[Root] = 2;for(scanf("%d", &n); n--;) {scanf("%s", str);if(str[0] == '+') sscanf(str+1, "%s", s + 1), scanf("%I64d", &Dat), INSERT(s, Dat);else if(str[1] >= '0'&&str[1] <= '9') sscanf(str + 1, "%d", &LDat), QUERY(LDat);else sscanf(str + 1, "%s", s + 1), QUERY(s);}}int main() {#ifndef ONLINE_JUDGESETIO("1056");#endifSolve();return 0;}
?
