HDU 3436 Queue-jumpers

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和query的点取出来，把其他区间都离散化成点，每次top是不会改变那些区间的，所以splay直接上就好了，为了防溢出在右端再加一个点。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 3e5 + 10;
int n, m, root, T, a[maxn], tot, dis, c[maxn], b[maxn], z = 0;
char s[10];
map<int, int> M;

struct Splays
{
  const static int maxn = 3e5 + 10;     //节点个数
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右儿子，父亲节点和节点总个数
  int A[maxn], C[maxn], L[maxn];
  int Node(int f, int l, int u) { C[sz] = A[sz] = u; L[sz] = l; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; A[sz] = u; return sz++; }//申请一个新节点
  void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; }//清空操作
  void rotate(int x, int k)
  {
    int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
    if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
    F[x] = F[y];    F[y] = x; ch[x][k] = y;
    C[x] = C[y];  C[y] = C[ch[y][0]] + C[ch[y][1]] + A[y];
  }
  void Splay(int x, int r)
  {
    for (int fa = F[r]; F[x] != fa;)
    {
      if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
      int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
      y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
    }
  }
  void build(int fa, int &x, int l, int r)
  {
    if (l > r) return;
    int mid = l + r >> 1;
    x = Node(fa, b[mid], c[mid]);
    if (c[mid] == 1) M[b[mid]] = x;
    build(x, ch[x][0], l, mid - 1);
    build(x, ch[x][1], mid + 1, r);
    C[x] += C[ch[x][0]] + C[ch[x][1]];
  }
  void up(int&x, int y)
  {
    Splay(M[y], x); x = M[y];
    for (int i = ch[x][1]; i; i = ch[i][0])
    {
      if (!ch[i][0]){ Splay(i, x); x = i; break; }
    }
    int temp = ch[x][0];  ch[x][0] = ch[temp][0]; F[ch[x][0]] = x;
    F[temp] = 0;  ch[temp][0] = 0;  C[x] -= C[temp];
    for (int i = x; i; i = ch[i][0])
    {
      if (!ch[i][0]){ Splay(i, x); x = i; break; }
    }
    ch[temp][1] = x;  F[x] = temp;
    C[temp] = A[temp] + C[x]; x = temp;
  }
  void findsa(int&x, int y)
  {
    Splay(M[y], x); x = M[y];
    printf("%d\n", C[ch[x][0]] + 1);
  }
  void findrk(int&x, int y)
  {
    for (int i = x; i;)
    {
      if (C[ch[i][0]] >= y) { i = ch[i][0]; continue; }
      if (C[ch[i][0]] + A[i] >= y) { printf("%d\n", L[i] + y - C[ch[i][0]] - 1); return; }
      y -= A[i] + C[ch[i][0]];  i = ch[i][1]; 
    }
  }
}solve;

struct point
{
  int x, y;
}q[maxn];

int main()
{
  cin >> T;
  while (T--)
  {
    scanf("%d%d", &n, &m);
    M.clear();  dis = tot = root = 0;
    solve.clear();  
    for (int i = 0; i < m; i++)
    {
      scanf("%s%d", s, &q[i].y);
      q[i].x = (s[0] == 'T' ? 0 : s[0] == 'Q' ? 1 : 2);
      if (q[i].x < 2) a[tot++] = q[i].y;
    }
    sort(a, a + tot);
    tot = unique(a, a + tot) - a;
    for (int i = 0, j = 1; i < tot; i++)
    {
      if (a[i]>j) { b[dis] = j; c[dis++] = a[i] - j; }
      b[dis] = a[i]; c[dis++] = 1;  j = a[i] + 1;
    }
    if (a[tot - 1] < n) { b[dis] = a[tot - 1] + 1; c[dis++] = n - a[tot - 1]; }
    b[dis] = n + 1; c[dis] = 0;
    solve.build(0, root, 0, dis);
    printf("Case %d:\n", ++z);
    for (int i = 0; i < m; i++)
    {
      switch (q[i].x)
      {
        case 0:solve.up(root, q[i].y); break;
        case 1:solve.findsa(root, q[i].y); break;
        case 2:solve.findrk(root, q[i].y); break;
      }
    }
  }
  return 0;
}