bzoj 1862/1056 [HAOI2008]排名系统

原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1862

很恶心的一道题，我也不晓得自己是第几次写这题了%>_<%。

写了两种方法，平衡树+哈希和平衡树+map。哈希函数是抄别人的。比较了一下还是哈希快一些。

题意很简单，就不说了。

具体思路是，平衡树维护排名，map建立姓名和分数一一对应的关系。

求rank时题意默认是越先提交得分排名越靠前(相同得分的条件下)。

具体如下：

平衡树+map

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<string>
  7 #include<map>
  8 using std::min;
  9 using std::map;
 10 using std::string;
 11 const int Max_N = 260000;
 12 char src[Max_N][12];
 13 typedef char State[100];
 14 struct Node{
 15     int v, s, t, id;
 16     Node *ch[2];
 17     inline void set(int _v = 0, int _s = 0, int _t = 0, int _id = 0, Node *p = NULL){
 18         ch[0] = ch[1] = p;
 19         v = _v, s = _s, t = _t, id = _id;
 20     }
 21     inline void push_up(){
 22         s = ch[0]->s + ch[1]->s + 1;
 23     }
 24     inline int cmp(int _v, int _t) const{
 25         if (v == _v){
 26             return t == _t ? -1 : _t > t;
 27         }
 28         return v > _v;
 29     }
 30 };
 31 struct SizeBalanceTree{
 32     Node stack[Max_N];
 33     Node *root, *null, *tail;
 34     Node *store[Max_N];
 35     int top;
 36     void init(){
 37         tail = &stack[0];
 38         null = tail++;
 39         null->set();
 40         root = null;
 41         top = 0;
 42     }
 43     inline Node *newNode(int v, int t, int id){
 44         Node *p = null;
 45         if (top) p = store[--top];
 46         else p = tail++;
 47         p->set(v, 1, t, id, null);
 48         return p;
 49     }
 50     inline void rotate(Node* &x, int d){
 51         Node *k = x->ch[!d];
 52         x->ch[!d] = k->ch[d];
 53         k->ch[d] = x;
 54         k->s = x->s;
 55         x->push_up();
 56         x = k;
 57     }
 58     inline void Maintain(Node* &x, int d){
 59         if (x->ch[d] == null) return;
 60         if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
 61             rotate(x, !d);
 62         } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
 63             rotate(x->ch[d], d), rotate(x, !d);
 64         } else {
 65             return;
 66         }
 67         Maintain(x, 0), Maintain(x, 1);
 68     }
 69     inline void insert(Node* &x, int v, int t, int id){
 70         if (x == null){
 71             x = newNode(v, t, id);
 72             return;
 73         } else {
 74             x->s++;
 75             int d = x->cmp(v, t);
 76             insert(x->ch[d], v, t, id);
 77             x->push_up();
 78             Maintain(x, d);
 79         }
 80     }
 81     inline void del(Node*  &x, int v, int t){
 82         if (x == null) return;
 83         x->s--;
 84         int d = x->cmp(v, t);
 85         if (-1 == d){
 86             if (!x->ch[0]->s || !x->ch[1]->s){
 87                 store[top++] = x;
 88                 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
 89             } else {
 90                 Node *ret = x->ch[1];
 91                 for (; ret->ch[0] != null; ret = ret->ch[0]);
 92                 x->v = ret->v, x->t = ret->t, x->id = ret->id;
 93                 del(x->ch[1], ret->v, ret->t);
 94             }
 95         } else {
 96             del(x->ch[d], v, t);
 97         }
 98         if (x != null) x->push_up();
 99     }
100     inline int find(Node *x, int v, int t){
101         int k = 0, cur = 0;
102         for (; x != null;){
103             int d = x->cmp(v, t);
104             k = x->ch[0]->s;
105             if (-1 == d) break;
106             else if (!d) x = x->ch[0];
107             else cur += k + 1, x = x->ch[1];
108         }
109         return cur + k + 1;
110     }
111     inline int rank(Node *x, int k){
112         for (; x != null;){
113             int t = x->ch[0]->s;
114             if (k == t + 1) break;
115             else if (k <= t) x = x->ch[0];
116             else k -= t + 1, x = x->ch[1];
117         }
118         return x->id;
119     }
120     inline void insert(int v, int t, int id){
121         insert(root, v, t, id);
122     }
123     inline void del(int v, int t){
124         del(root, v, t);
125     }
126     inline int find(int v, int t){
127         return find(root, v, t);
128     }
129     inline int rank(int k){
130         return rank(root, k);
131     }
132 }sbt;
133 struct node{ 
134     int v, t, id; 
135     node(){};
136     node(int _v, int _t, int _id) :v(_v), t(_t), id(_id){}
137 };
138 map<string, node > stri;
139 void gogo(char *s, int v, int t, int &tot){
140     string str(s);
141     if (stri.count(str) != 0){
142         sbt.del(stri[str].v, stri[str].t);
143         stri[str].v = v, stri[str].t = t;
144         sbt.insert(v, t, stri[str].id);
145         return;
146     }
147     strcpy(src[++tot], s);
148     sbt.insert(v, t, tot);
149     node ret(v, t, tot);
150     stri[str] = ret;
151 }
152 int main(){
153 #ifdef LOCAL
154     freopen("in.txt", "r", stdin);
155     freopen("out.txt", "w+", stdout);
156 #endif
157     sbt.init();
158     State s1, buf;
159     int n, v, tot = 0;
160     scanf("%d
", &n);
161     for (int i = 1; i <= n; i++){
162         gets(buf);
163         if (buf[0] == '+'){
164             sscanf(&buf[1], "%s %d", s1, &v);
165             gogo(s1, v, i, tot);
166         } else if (buf[0] == '?' && isalpha(buf[1])){
167             sscanf(&buf[1], "%s", s1);
168             printf("%d
", sbt.find(stri[s1].v, stri[s1].t));
169         } else {
170             int ed;
171             sscanf(&buf[1], "%d", &v);
172             ed = min(v + 9, tot);
173             for (int j = v; j <= ed; j++) {
174                 printf("%s%c", src[sbt.rank(j)], j != ed ? ' ' : '
');
175             }
176         }
177     }    
178     return 0;
179 }

View Code

平衡树+哈希

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<string>
  7 #include<map>
  8 using std::min;
  9 using std::pair;
 10 using std::string;
 11 typedef char State[100];
 12 typedef unsigned long long ull;
 13 const int Max_N = 260000;
 14 struct Node{
 15     int v, s, t, id;
 16     Node *ch[2];
 17     inline void
 18     set(int _v = 0, int _s = 0, int _t = 0, int _id = 0, Node *p = NULL){
 19         ch[0] = ch[1] = p;
 20         v = _v, s = _s, t = _t, id = _id;
 21     }
 22     inline void push_up(){
 23         s = ch[0]->s + ch[1]->s + 1;
 24     }
 25     inline int cmp(int _v, int _t) const{
 26         if (v == _v){
 27             return t == _t ? -1 : _t > t;
 28         }
 29         return v > _v;
 30     }
 31 };
 32 struct SizeBalanceTree{
 33     Node stack[Max_N];
 34     Node *root, *null, *tail;
 35     Node *store[Max_N];
 36     int top;
 37     void init(){
 38         tail = &stack[0];
 39         null = tail++;
 40         null->set();
 41         root = null;
 42         top = 0;
 43     }
 44     inline Node *newNode(int v, int t, int id){
 45         Node *p = null;
 46         if (top) p = store[--top];
 47         else p = tail++;
 48         p->set(v, 1, t, id, null);
 49         return p;
 50     }
 51     inline void rotate(Node* &x, int d){
 52         Node *k = x->ch[!d];
 53         x->ch[!d] = k->ch[d];
 54         k->ch[d] = x;
 55         k->s = x->s;
 56         x->push_up();
 57         x = k;
 58     }
 59     inline void Maintain(Node* &x, int d){
 60         if (x->ch[d] == null) return;
 61         if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
 62             rotate(x, !d);
 63         } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
 64             rotate(x->ch[d], d), rotate(x, !d);
 65         } else {
 66             return;
 67         }
 68         Maintain(x, 0), Maintain(x, 1);
 69     }
 70     inline void insert(Node* &x, int v, int t, int id){
 71         if (x == null){
 72             x = newNode(v, t, id);
 73             return;
 74         } else {
 75             x->s++;
 76             int d = x->cmp(v, t);
 77             insert(x->ch[d], v, t, id);
 78             x->push_up();
 79             Maintain(x, d);
 80         }
 81     }
 82     inline void del(Node*  &x, int v, int t){
 83         if (x == null) return;
 84         x->s--;
 85         int d = x->cmp(v, t);
 86         if (-1 == d){
 87             if (!x->ch[0]->s || !x->ch[1]->s){
 88                 store[top++] = x;
 89                 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
 90             } else {
 91                 Node *ret = x->ch[1];
 92                 for (; ret->ch[0] != null; ret = ret->ch[0]);
 93                 x->v = ret->v, x->t = ret->t, x->id = ret->id;
 94                 del(x->ch[1], ret->v, ret->t);
 95             }
 96         } else {
 97             del(x->ch[d], v, t);
 98         }
 99         if (x != null) x->push_up();
100     }
101     inline int find(Node *x, int v, int t){
102         int k = 0, cur = 0;
103         for (; x != null;){
104             int d = x->cmp(v, t);
105             k = x->ch[0]->s;
106             if (-1 == d) break;
107             else if (!d) x = x->ch[0];
108             else cur += k + 1, x = x->ch[1];
109         }
110         return cur + k + 1;
111     }
112     inline int rank(Node *x, int k){
113         for (; x != null;){
114             int t = x->ch[0]->s;
115             if (k == t + 1) break;
116             else if (k <= t) x = x->ch[0];
117             else k -= t + 1, x = x->ch[1];
118         }
119         return x->id;
120     }
121     inline void insert(int v, int t, int id){
122         insert(root, v, t, id);
123     }
124     inline void del(int v, int t){
125         del(root, v, t);
126     }
127     inline int find(int v, int t){
128         return find(root, v, t);
129     }
130     inline int rank(int k){
131         return rank(root, k);
132     }
133 }sbt;
134 #define BASE 133
135 #define MOD 299997
136 #define MAXN 500000
137 int now[Max_N], _time[Max_N];
138 struct HashSet{
139     int head[MAXN];
140     int tot, next[MAXN];
141     ull hash[MAXN];
142     char src[Max_N][12];
143     inline ull GetHash(char *s){
144         ull re = 0;
145         while (*s != '') re = re * BASE + *s++;
146         return re;
147     }
148     inline int Insert(char *s) {
149         ull _hash = GetHash(s);
150         int x = _hash % MOD;
151         for (int i = head[x]; i; i = next[i]){
152             if (hash[i] == _hash) return i;
153         }
154         next[++tot] = head[x];
155         hash[tot] = _hash;
156         head[x] = tot;
157         strcpy(src[tot], s);
158         return tot;
159     }
160 }map;
161 int main(){
162 #ifdef LOCAL
163     freopen("in.txt", "r", stdin);
164     freopen("out.txt", "w+", stdout);
165 #endif
166     int n, v;
167     sbt.init();
168     State s1, buf;
169     scanf("%d
", &n);
170     for (int i = 1; i <= n; i++){
171         gets(buf);
172         if (buf[0] == '+'){
173             sscanf(&buf[1], "%s %d", s1, &v);
174             int x = map.Insert(s1);
175             if (now[x])    sbt.del(now[x], _time[x]);
176             now[x] = v, _time[x] = i;
177             sbt.insert(now[x], _time[x], x);
178         } else if (buf[0] == '?' && isalpha(buf[1])){
179             sscanf(&buf[1], "%s", s1);
180             int x = map.Insert(s1);
181             printf("%d
", sbt.find(now[x], _time[x]));
182         } else {
183             int ed;
184             sscanf(&buf[1], "%d", &v);
185             ed = min(v + 9, map.tot);
186             for (int j = v; j <= ed; j++) {
187                 printf("%s%c", map.src[sbt.rank(j)], j != ed ? ' ' : '
');
188             }
189         }
190     }
191     return 0;
192 }

View Code

By: GadyPu 博客地址：http://www.cnblogs.com/GadyPu/ 转载请说明