【洛谷 P4291】 [HAOI2008]排名系统（Splay，Trie）-白红宇

【洛谷 P4291】 [HAOI2008]排名系统（Splay，Trie）

阅读量：5061 次

发布时间：2019-06-12

本文共 4220 字，大约阅读时间需要 14 分钟。

不是双倍经验我会去\(debug\)一上午?

一开始我是用的\(map+string\)，跑的太慢了，T了4个点。

后来我手写了\(string\)，重载了小于号，依然用的\(map\)，T了2个点。

然后我加入各种卡常，发现没有用。

\(\cdots\)

然后我把手写\(string\)改成字符串哈希，依然用\(map\)存，还是\(T\)了2个点。

然后继续各种优化，没有用。

然后去看\(yyb\)聚聚的题解，原来可以每操作几百次随机\(Splay\)一下来保证树的随机性，只\(T\)了一个点了。

我去\(BZOJ\)离线题库上把这题数据下载下来，我觉得应该是最大的那个极限数据\(n=250000\)的点T了。

于是开文件本机上了试了下，跑了\(1.03-1.2s\)之间。

然后我疯狂改随机数种子，发现根本没什么用。

\(\cdots\)

后来又把\(map+\)字符串哈希改成了字典树，跑的飞快

最大的点本机\(0.7s\)左右，没理由跑不过啊

但交到洛谷上还是T

交到BZOJ上还是T

交到CJOJ上还是T

交到CodeVS上还是T

诶，CodeVS上显示TLE的点，\(n=130000\)

？？？？？？？

于是找到\(BZOJ\)数据里的那个点，woc

原来有人的分数超过了\(999999999\)，也就是我设的\(INF\)，也就是\(Splay\)中2个虚点的值。

\(\cdots\)

直接超过了，这也太猛了。

然后虚点不是最大了，\(GG\)了。

看来\(INF\)还是要写成\(2147483647\)啊。

果然，改了\(INF\)后跑的飞快，总共才跑了\(479ms\)

~~吊打pbds~~

突然发现\(Splay\)好容易写

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #pragma GCC optimize(2)using namespace std;const int MAXN = 250010;inline int read(){ int s = 0; char ch = getchar(); while(ch < '0' || ch > '9')ch = getchar(); while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s;}struct info{ int val, id; int operator > (const info A) const{ return val == A.val ? id < A.id : val > A.val; }};struct splay{ info val; int size, ch[2], fa;}t[MAXN];int root, num, T;struct Trie{ int val; Trie *ch[26]; Trie(){ for(int i = 0; i < 26; ++i) ch[i] = NULL; val = 0; }}rt;int Insert(char *s, int pos){ int len = strlen(s); Trie *u = &rt; for(int i = 0; i < len; ++i){ if(u->ch[s[i] - 'A'] == NULL) u->ch[s[i] - 'A'] = new Trie(); u = u->ch[s[i] - 'A']; } if(u->val) return u->val; u->val = pos; return 0;}inline void pushup(int x){ t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + 1;}inline void rotate(int x){ int y = t[x].fa, z = t[y].fa, k = t[y].ch[1] == x; t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y; t[y].fa = x; t[x].ch[k ^ 1] = y; t[x].fa = z; t[z].ch[t[z].ch[1] == y] = x; pushup(y); pushup(x);}inline void Splay(int x, int goal){ int y, z; while(t[x].fa != goal){ y = t[x].fa; z = t[y].fa; if(z != goal) rotate((t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? x : y); rotate(x); } if(!goal) root = x;}inline int insert(info x, int num){ if(!root){ root = num; t[root].val = x; t[root].size = 1; return root; } int u = root, fa = 0; while(u){ fa = u; u = t[u].ch[x > t[u].val]; } int id = num; t[id].val = x; t[id].size = 1; t[id].fa = fa; if(fa) t[fa].ch[x > t[fa].val] = id; Splay(id, 0); return id;}int limit, tmp, Time;void find(int x){ int u = root; while(233){ if(t[t[u].ch[0]].size == x - 1) break; if(t[t[u].ch[0]].size >= x) u = t[u].ch[0]; else x -= t[t[u].ch[0]].size + 1, u = t[u].ch[1]; } Splay(u, 0);}char ch, name[MAXN][12];int len[MAXN];void dfs(int x){ if(!limit) return; if(t[x].ch[1]) dfs(t[x].ch[1]); if(!limit) return; for(int i = 0; i < len[x]; ++i) putchar(name[x][i]); putchar(' '); --limit; if(t[x].ch[0]) dfs(t[x].ch[0]);}int next(int x, int mode){ Splay(x, 0); int u = t[root].ch[mode]; while(t[u].ch[!mode]) u = t[u].ch[!mode]; return u;}char s[12];int pq;int main(){ //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); T = read(); insert((info){ -2147483646, 9999999 }, ++num); insert((info){ 2147483646, -1 }, ++num); while(T--){ ch = getchar(); while(ch != '+' && ch != '?') ch = getchar(); if(ch == '+'){ scanf("%s", s); if(pq = Insert(s, num + 1)){ int l = next(pq, 0), r = next(pq, 1); Splay(l, 0); Splay(r, l); t[t[root].ch[1]].ch[0] = 0; Splay(t[root].ch[1], 0); insert((info){ read(), ++Time }, pq); } else{ insert((info){read(), ++Time}, ++num); memcpy(name[num], s, sizeof s); len[num] = strlen(name[num]); } } if(ch == '?'){ ch = getchar(); if(ch >= '0' && ch <= '9'){ tmp = 0; while(ch >= '0' && ch <= '9'){ tmp = tmp * 10 + ch - '0'; ch = getchar(); } find(num - tmp); for(int i = 0; i < len[root]; ++i) putchar(name[root][i]); putchar(' '); limit = 9; if(t[root].ch[0]) dfs(t[root].ch[0]); printf("\n"); } else{ int p = 0; while(ch >= 'A' && ch <= 'Z'){ s[p++] = ch; ch = getchar(); } for(int i = p; i < 12; ++i) s[i] = 0; Splay(Insert(s, 233), 0); printf("%d\n", t[t[root].ch[1]].size); } } if(T % 200 == 0) Splay(rand() % num + 1, 0); } return 0;}