中等难度的数据结构题，不过数据范围大，所以要hash操作过的数列。1y～
题意就像题目一样，模拟一队人，其中有人插队，询问某个时刻，第x个人的编号或编号为x的人的位置。
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 struct Node { 10 int l, r; 11 int cnt; 12 Node *c[2], *p; 13 14 Node (int _cnt = 0, int _l = 0, int _r = -1) { 15 l = _l; 16 r = _r; 17 cnt = _cnt; 18 c[0] = c[1] = p = NULL; 19 } 20 } *Null, *Root, *Head; 21 22 void up(Node *rt) { 23 rt->cnt = rt->c[0]->cnt + rt->c[1]->cnt + (rt->r - rt->l + 1); 24 } 25 26 void rotate(Node *x, bool right) { 27 Node *y = x->p; 28 29 y->c[!right] = x->c[right]; 30 if (x->c[right] != Null) { 31 x->c[right]->p = y; 32 } 33 x->p = y->p; 34 if (y->p != Null) { 35 if (y->p->c[0] == y) { 36 y->p->c[0] = x; 37 } else { 38 y->p->c[1] = x; 39 } 40 } 41 x->c[right] = y; 42 y->p = x; 43 up(y); 44 45 if (Root == y) Root = x; 46 } 47 48 void splay(Node *x, Node *f) { 49 while (x->p != f) { 50 if (x->p->p == f) { 51 if (x->p->c[0] == x) rotate(x, 1); 52 else rotate(x, 0); 53 } else { 54 Node *y = x->p, *z = y->p; 55 56 if (z->c[0] == y) { 57 if (y->c[0] == x) { 58 rotate(y, 1); 59 rotate(x, 1); 60 } else { 61 rotate(x, 0); 62 rotate(x, 1); 63 } 64 } else { 65 if (y->c[0] == x) { 66 rotate(x, 1); 67 rotate(x, 0); 68 } else { 69 rotate(y, 0); 70 rotate(x, 0); 71 } 72 } 73 } 74 } 75 76 up(x); 77 } 78 79 const int inf = 0x7f7f7f7f; 80 81 void initSplay() { 82 Null = new Node(); 83 Root = Head = new Node(1, 0, 0); 84 85 Root->p = Root->c[0] = Null; 86 Root->c[1] = new Node(1, inf, inf); 87 Root->c[1]->p = Root; 88 Root->c[1]->c[0] = Root->c[1]->c[1] = Null; 89 up(Root); 90 } 91 92 void in_tra(Node *rt) { 93 if (rt == Null) { 94 return ; 95 } 96 in_tra(rt->c[0]); 97 printf("%d %d %d %d %d %d %d\n", rt->l, rt->r, rt->cnt, rt, rt->p, rt->c[0], rt->c[1]); 98 in_tra(rt->c[1]); 99 }100 101 const int maxn = 100005;102 const int HASH = 0x55555555;103 const int hashMod = 400009;104 105 char op[maxn][6];106 int num[maxn], hash[hashMod], hashPos[hashMod];107 108 void initHash() {109 memset(hashPos, 0, sizeof(hashPos));110 }111 112 void insHash(int x, int pos) {113 int p = (x ^ HASH) % hashMod;114 115 while (hash[p] != x && hashPos[p]) {116 p++;117 if (p >= hashMod) p -= hashMod;118 }119 120 hash[p] = x;121 hashPos[p] = pos;122 }123 124 int getHash(int x) {125 int p = (x ^ HASH) % hashMod;126 127 while (hash[p] != x && hashPos[p]) {128 p++;129 if (p >= hashMod) p -= hashMod;130 }131 132 return hashPos[p];133 }134 135 Node *rec[maxn << 1];136 137 void insSplay(Node *x) {138 x->c[1] = Root->c[1];139 Root->c[1]->p = x;140 Root->c[1] = x;141 x->p = Root;142 x->c[0] = Null;143 144 splay(x, Null);145 }146 147 void build(int n, int m) {148 set used;149 150 initSplay();151 used.clear();152 for (int i = 0; i < m; i++) {153 scanf("%s%d", op[i], &num[i]);154 if (op[i][0] == 'T' || op[i][0] == 'Q') {155 used.insert(num[i]);156 }157 }158 159 int last = 0, cnt = 0;160 161 for (set ::iterator si = used.begin(); si != used.end(); si++) {162 // printf("%d\n", *si);163 if (last + 1 < *si) {164 rec[++cnt] = new Node(1, last + 1, *si - 1);165 // printf("add %d %d\n", last + 1, *si - 1);166 insSplay(rec[cnt]);167 }168 rec[++cnt] = new Node(1, *si, *si);169 // printf("add %d\n", *si);170 insSplay(rec[cnt]);171 172 insHash(*si, cnt);173 last = *si;174 }175 if (last < n) {176 rec[++cnt] = new Node(1, last + 1, n);177 // printf("add %d %d\n", last + 1, n);178 insSplay(rec[cnt]);179 }180 181 // printf("cnt %d\n", cnt);182 // puts("built!");183 }184 185 int getPos(int x) {186 Node *rt = rec[getHash(x)];187 188 splay(rt, Null);189 190 return rt->c[0]->cnt;191 }192 193 int getPer(int pos) {194 Node *p = Root;195 196 pos++;197 while (true) {198 int cnt = p->c[0]->cnt;199 200 if (cnt + 1 <= pos && pos <= cnt + (p->r - p->l + 1)) {201 pos -= cnt;202 203 return p->l + pos - 1;204 } else if (pos <= cnt) {205 // puts("left");206 p = p->c[0];207 } else {208 // puts("right");209 pos -= cnt + (p->r - p->l + 1);210 p = p->c[1];211 }212 }213 }214 215 Node *preNode(Node *x) {216 splay(x, Null);217 x = x->c[0];218 while (x->c[1] != Null) x = x->c[1];219 220 return x;221 }222 223 Node *postNode(Node *x) {224 splay(x, Null);225 x = x->c[1];226 while (x->c[0] != Null) x = x->c[0];227 228 return x;229 }230 231 void Top(int x) {232 x = getHash(x);233 // printf("x %d\n", x);234 235 Node *pl = preNode(rec[x]);236 Node *pr = postNode(rec[x]);237 238 splay(pl, Null);239 splay(pr, pl);240 241 // cut node242 Node *tmp = pr->c[0];243 pr->c[0] = Null;244 splay(pr, Null);245 // top node246 splay(Head, Null);247 insSplay(tmp);248 }249 250 void process(int m) {251 for (int i = 0; i < m; i++) {252 switch (op[i][0]) {253 case 'T':254 // puts("Top");255 Top(num[i]);256 break;257 case 'Q':258 // puts("Query");259 printf("%d\n", getPos(num[i]));260 break;261 case 'R':262 // puts("Rank");263 printf("%d\n", getPer(num[i]));264 break;265 }266 }267 }268 269 int main() {270 int T;271 272 // freopen("in", "r", stdin);273 scanf("%d", &T);274 for (int i = 1; i <= T; i++) {275 int n, m;276 277 scanf("%d%d", &n, &m);278 build(n, m);279 printf("Case %d:\n", i);280 process(m);281 }282 283 return 0;284 }
——written by Lyon