對應HDU題目：點選打開連結
Queue-jumpers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2754 Accepted Submission(s): 711
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
題意：
有三種操作：Top x（将x提到第一位）， Query x（詢問元素x在第幾位）， Rank k （詢問第k位的元素是誰）。
思路：
可以用伸展樹實作。n有10^8那麼大，而q隻有10^5，是以應該離散化把Top和Query的操作數作為點，把他們之間的區間也作為點（區間内部的點不需要移動，是以可以這樣），這樣最多有200000左右的結點。
Top X ：把X伸展到根，删掉X，在樹的左下角添加結點X。
Query X ：把X伸展到根，則sz[Left[T]] + 1就是結果
Rand X ：從根開始根據情況往左右兩邊找
伸展樹隻需要儲存子樹的所有點（加上區間的所有點），以a[]數組的下标作為結點編号，對于Top和Query操作，可以通過二分查找确定結點編号。
C++ AC，G++ RE代碼：
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define N 200024
#define nil (0x7fffffff)
using namespace std;
int Left[N];
int Right[N];
int fa[N];
int sz[N]; //以i為根的子樹的結點數
int b[N>>1];
char Q[N>>1][7];
int X[N>>1];
typedef struct
{
int first, second;
}PAIR;
PAIR a[N]; //映射數組
int len;
//初始化
void Build(int pre, int &T, int x, int y)
{
int mid = ((x + y)>>1);
T = mid;
fa[T] = pre;
Left[T] = Right[T] = nil;
sz[T] = a[T].second;
if(x == y) return;
if(x < mid){
Build(T, Left[T], x, mid - 1);
sz[T] += sz[Left[T]];
}
if(mid < y){
Build(T, Right[T], mid + 1, y);
sz[T] += sz[Right[T]];
}
}
void R_rotate(const int x)
{
const int y = fa[x];
const int z = fa[y];
const int k = Right[x];
int sx = sz[x], sy = sz[y], sk = 0;
if(nil != k) sk = sz[k];
Left[y] = k;
Right[x] = y;
if(nil != z){
if(y == Left[z]) Left[z] = x;
else Right[z] = x;
}
if(nil != k) fa[k] = y;
fa[y] = x;
fa[x] = z;
sz[y] = sy - sx + sk;
sz[x] = sx - sk + sz[y];
}
void L_rotate(const int x)
{
const int y = fa[x];
const int z = fa[y];
const int k = Left[x];
int sx = sz[x], sy = sz[y], sk = 0;
if(nil != k) sk = sz[k];
Right[y] = k;
Left[x] = y;
if(nil != z){
if(y == Right[z]) Right[z] = x;
else Left[z] = x;
}
if(nil != k) fa[k] = y;
fa[y] = x;
fa[x] = z;
sz[y] = sy - sx + sk;
sz[x] = sx - sk + sz[y];
}
int Find(int x)
{
int l = 1, r = len, mid;
while(l <= r)
{
mid = ((l + r)>>1);
if(a[mid].first == x) return mid;
else if(a[mid].first < x) l = mid + 1;
else r = mid - 1;
}
return -1;
}
void Splay(int x, int &T)
{
if(nil == T) return;
int p, end;
end = fa[T];
p = x;
while(end != fa[x])
{
p = fa[x];
if(end == fa[p]){ //p是根結點
if(x == Left[p]) R_rotate(x);
else L_rotate(x);
break;
}
//p不是根結點
if(x == Left[p]){
if(p == Left[fa[p]]){
R_rotate(p); //LL
R_rotate(x); //LL
}
else{
R_rotate(x); //RL
L_rotate(x);
}
}
else{
if(p == Right[fa[p]]){ //RR
L_rotate(p);
L_rotate(x);
}
else{ //LR
L_rotate(x);
R_rotate(x);
}
}
}
T = x;
}
//在隊首添加結點
void Add_at_lower_left_corner(int x, int T)
{
int p = T;
sz[p]++;
while(nil != Left[p]){
p = Left[p];
sz[p]++;
}
Left[p] = x;
sz[x] = 1;
fa[x] = p;
Left[x] = Right[x] = nil;
}
void Delete_root(int &T)
{
if(nil == T) return;
int l, r, x;
l = Left[T];
r = Right[T];
if(nil == l && nil == r){
T = nil;
return;
}
if(nil != l) fa[l] = nil;
if(nil != r) fa[r] = nil;
if(nil == l){ //沒有左兒子
T = r;
return;
}
if(nil == r){ //沒有右兒子
T = l;
return;
}
x = l;
while(nil != Right[x])
x = Right[x]; //x為T的左子樹的中序最大值結點(右下角結點)
Splay(x, l); //把x伸展到左子樹的根結點
T = l; //把左子樹的根作為整棵樹的根，此時T沒有右子樹
//接上右子樹
Right[T] = r;
if(nil != r){
fa[r] = T;
sz[T] += sz[r];//更新結點數
}
}
void Top(int x, int &T)
{
x = Find(x);
Splay(x, T); //把x結點伸展到根
if(nil == Left[T]) return; //新根沒有左兒子，根即為第一個數
Delete_root(T); //删除根結點
Add_at_lower_left_corner(x, T); //在T的左下角增加結點x
Splay(x, T);
}
int Rand(int x, int T)
{
if(nil == T) return 0;
int sum, p;
p = T;
sum = (nil == Left[p] ? 0 : sz[Left[p]]) + a[p].second;
while(sum != x)
{
if(sum > x){
if(x < sz[Left[p]] + 1) p = Left[p];
else return a[p].first - (sum - x);
}
else{
x -= sum;
p = Right[p];
}
if(nil == p) return 0;
sum = (nil == Left[p] ? 0 : sz[Left[p]]) + a[p].second;
}
return a[p].first;
}
int Query(int x, int &T)
{
x = Find(x);
if(nil == T) return 0;
Splay(x, T);
return (nil == Left[x] ? 0 : sz[Left[x]]) + 1;
}
//離散化
void Discrete(int n, int j)
{
int i, k;
sort(b + 1, b + j + 1);
k = 1;
for(i = 2; i <= j; i++) //去重
if(b[i] != b[k]) b[++k] = b[i];
len = 0;
for(i = 1; i <= k; i++){
if(b[i] - b[i-1] > 1){
a[++len].first = b[i] - 1;
a[len].second = b[i] - b[i-1] - 1;
}
a[++len].first = b[i];
a[len].second = 1;
}
if(b[k] < n){
a[++len].first = n;
a[len].second = n - b[k];
}
}
int main()
{
//freopen("in.txt","r",stdin);
int T, t, n, q, w = 0;
int i, j;
scanf("%d", &t);
while(t--)
{
printf("Case %d:\n", ++w);
scanf("%d%d", &n, &q);
j = 0;
for(i = 0; i < q; i++){
scanf("%s%d", Q[i], &X[i]);
if('T' == Q[i][0] || 'Q' == Q[i][0])
b[++j] = X[i];
}
Discrete(n, j); //離散化
Build(nil, T, 1, len);
for(i = 0; i < q; i++){
if('T' == Q[i][0]) Top(X[i], T);
else if('Q' == Q[i][0]) printf("%d\n", Query(X[i], T));
else printf("%d\n", Rand(X[i], T));
}
}
return 0;
}
![WPF 中TreeView 的動态加載和自定義布局（圖檔+文字）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)