HDU 3436 Queue-jumpers Splay 离散化

Posted on | In | Comments: | Views:

Queue-jumpers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Ponyo and Garfield are waiting outside the box-office for their favorite movie. Because queuing is so boring, that they want to play a game to kill the time. The game is called “Queue-jumpers”. Suppose that there are N people numbered from 1 to N stand in a line initially. Each time you should simulate one of the following operations:

  1. Top x :Take person x to the front of the queue
  2. Query x: calculate the current position of person x
  3. Rank x: calculate the current person at position x

Where x is in [1, N].

Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.

Input

In the first line there is an integer T, indicates the number of test cases.(T<=50)

In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.

Output

For each test case, output “Case d:“ at first line where d is the case number counted from one, then for each “Query x” operation ,output the current position of person x at a line, for each “Rank x” operation, output the current person at position x at a line.

Sample Input

3
9 5
Top 1
Rank 3
Top 7
Rank 6
Rank 8
6 2
Top 4
Top 5
7 4
Top 5
Top 2
Query 1
Rank 6

Sample Output

Case 1:
3
5
8
Case 2:
Case 3:
3
6

题意

一个队列，初始时每个人从 1 到 n 按顺序标记，3 种操作：

Top x：把标号为 x 的人提到队列的第一位；

Query x：查询标号为 x 的人的当前位置；

Rank x：查询当前从左数第 x 个位置的人的标号是多少。

分析

队列的结构是一直在变的，所以要想低复杂度地解决，也必须要用动态的数据结构来存，Splay 这时候就体现出优势了。

对 1 到 n 按顺序构造出 Splay，然后开始处理请求：

Top x：提到队首相当于先把 x 这个节点从树中删除，然后再插入到队首，在 Splay 中可以用一种更加简单的操作来实现。把 x 旋转到根，如果 x 没有左子树，说明已经在队首了，否则把右子树的最左节点旋转到右子树的根，这样旋转完之后，右子树的根节点是没有左子树的，此时再把根（x）的左子树切下来连到右节点的左空位上即可。

Query x：把 x 旋转到根，左子树的 size 加 1 就是根节点当前的序号。

Rank x：查找第 x 个位置的节点号，也是二叉搜索树的基本操作。

关键在于这道题还有个坑点，N 的范围最大到了 10^8，略大，同时可以发现询问数只有 10^5，因此可以考虑用离散化把范围分拆一下。

离散化之后，每个树节点可以代表的 size 不再限于 1 了，这块得注意处理一下。Top 和 Query 都是对于原本的序号进行操作，因此这两个操作中的 x 需要作为离散化的标记，离散化之后这两个操作的处理也基本上是一样的。

Rank 操作的 x 不需要离散化，队列动态变动之后早就不是原本的顺序了。对于这个操作，需要对原本的进行一定改动，每个树节点能够代表的可能是多个队列点，首先用 x-size[sons[spt][0]] 算出要询问的队列点是当前树节点代表的队列点中的第几个，再根据当前树节点代表的队列点区间范围找出原本的序列号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: HDU 3436
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 100010

int op[MAXN], x[MAXN];

struct node
{
    int x, index;
};

bool sort_op(node a, node b)
{
    if (a.x == b.x) return a.index < b.index;
    else return a.x < b.x;
}

node nodelist[MAXN*2];

int sons[MAXN][2];
int father[MAXN], size[MAXN], data[MAXN], ori[MAXN];
bool flag[MAXN];
int spttail, spt;

void rotate(int x, int w) //rotate(node,0/1)
{
    int y = father[x];
    sons[y][!w] = sons[x][w];
    if (sons[x][w]) father[sons[x][w]] = y;
    father[x] = father[y];
    if (father[y]) sons[father[y]][y==sons[father[y]][1]] = x;
    sons[x][w] = y;
    father[y] = x;

    size[x] = size[y];
    size[y] = size[sons[y][0]]+size[sons[y][1]]+data[y];
}

void splay(int x, int y) //splay(node,position)
{
    while(father[x] != y)
    {
        if (father[father[x]] == y) rotate(x, x==sons[father[x]][0]);
        else
        {
            int t = father[x];
            int w = (sons[father[t]][0]==t);
            if (sons[t][w] == x) rotate(x, !w);
            else rotate(t, w);
            rotate(x, w);
        }
    }
    if (!y) spt=x;
}

void select(int x, int v, int p) //select(root, k, position)
{
    while(v<size[sons[x][0]]+1 || v>size[sons[x][0]]+data[x])
    {
        if (v <= size[sons[x][0]]) x = sons[x][0];
        else 
        {
            v -= size[sons[x][0]]+data[x];
            x = sons[x][1];
        }
    }
    splay(x, p);
}

void insert(int x)
{
    spttail ++;

    data[spttail] = x;
    sons[spttail][1] = 0;
    father[spttail] = 0;
    if (spttail > 1)
    {
        size[spttail] = size[spttail-1]+x;
        sons[spttail][0] = spttail-1;
        father[spttail-1] = spttail;
    } else
    {
        size[spttail] = x;
        sons[spttail][0] = 0;
    }
}

void out(int x)
{
    if (sons[x][0]) out(sons[x][0]);
    printf("%d ", x);
    if (sons[x][1]) out(sons[x][1]);
}

int main()
{
    freopen("in.txt", "r", stdin);

    int T;
    scanf("%d", &T);
    for (int tt=1;tt<=T;tt++)
    {
        printf("Case %d:\n", tt);

        int n, q;
        scanf("%d %d", &n, &q);

        // ....

        getchar();
        for (int i=0;i<q;i++)
        {
            char s[10];
            scanf("%s %d", &s, &x[i]);
            switch(s[0])
            {
                case 'T':
                    op[i] = 0;
                    break;
                case 'Q':
                    op[i] = 1;
                    break;
                case 'R':
                    op[i] = 2;
            }
            nodelist[i].x = x[i];
            nodelist[i].index = i;
        }

        sort(&nodelist[0], &nodelist[q], sort_op);

        int last = 0;
        spttail = 0;
        for (int i=0;i<q;i++)
        if (op[nodelist[i].index] != 2)
        {
            if (last < nodelist[i].x)
            {
                if (nodelist[i].x-last>1)
                {
                    insert(nodelist[i].x-last-1);
                    ori[spttail] = last+1;
                }
                insert(1);
                ori[spttail] = nodelist[i].x;
                last = nodelist[i].x;
            }
            x[nodelist[i].index] = spttail;
        }
        if (last < n)
        {
            insert(n-last);
            ori[spttail] = last+1;
        }
        spt = spttail;

        for (int i=0;i<q;i++)
        {
            switch(op[i])
            {
                case 0:
                    splay(x[i], 0);
                    if (sons[spt][0])
                    if (sons[spt][1])
                    {
                        int temp = sons[spt][1];
                        while (sons[temp][0]) temp = sons[temp][0];
                        splay(temp, spt);
                        sons[temp][0] = sons[spt][0];
                        sons[spt][0] = 0;
                        father[sons[temp][0]] = temp;
                        size[temp] = size[sons[temp][0]]+size[sons[temp][1]]+data[temp];
                        size[spt] = size[temp]+data[spt];
                    } else
                    {
                        sons[spt][1] = sons[spt][0];
                        sons[spt][0] = 0;
                    }
                    break;
                case 1:
                    splay(x[i], 0);
                    if (sons[spt][0]) printf("%d\n", size[sons[spt][0]]+1);
                    else printf("1\n");
                    break;
                case 2:
                    select(spt, x[i], 0);
                    printf("%d\n", x[i]-size[sons[spt][0]]+ori[spt]-1);
                    break;
            }
        }
    }
    
    return 0;
}
0%