HDU 2475 Box

Description

There are N boxes on the ground, which are labeled by numbers from 1 to N. The boxes are magical, the size of each one can be enlarged or reduced arbitrarily.

Jack can perform the “MOVE x y” operation to the boxes: take out box x; if y = 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.

In the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.

The picture below shows the state after Jack performs “MOVE 4 1”:

Then he performs “MOVE 3 0”, the state becomes:

During a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.

Input

Input contains several test cases.

For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.

Next line has N integers: a1, a2, a3, ... , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).

Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.

On the next M lines, each line contains a MOVE operation or a query:

1. MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.

2. QUERY x, 1 <= x <= N, output the root box of box x.

Output

For each query, output the result on a single line. Use a blank line to separate each test case.

Sample Input

2
0 1
5
QUERY 1
QUERY 2
MOVE 2 0
MOVE 1 2
QUERY 1
6
0 6 4 6 1 0
4
MOVE 4 1
QUERY 3
MOVE 1 4
QUERY 1

Sample Output

樹形轉線形，巧妙的利用dfs序列，然後就是splay維護序列的删除和插入問題了，好題啊。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, m, l, r, L[maxn], R[maxn], x, root;
char s[20];
vector<int> t[maxn], dfs;

void Scan(int &x)
{
  char ch;
  while ((ch = getchar()) > '9' || ch < '0');
  int res = ch - '0';
  while ((ch = getchar()) <= '9'&&ch >= '0') res = res * 10 + ch - '0';
  x = res;
}

struct Splays
{
  const static int maxn = 2e5 + 10;     //節點個數
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右兒子，父親節點和節點總個數
  int A[maxn];
  int Node(int f, int a) { A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; 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]; 
    if (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;
  }
  void Splay(int x, int r)
  {
    while (F[x] != r)
    {
      if (F[F[x]] == r) { 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 Dfs(int x)
  {
    if (x) dfs.push_back(x);
    for (int i = 0; i < t[x].size(); i++) Dfs(t[x][i]);
    if (x) dfs.push_back(-x);
  }
  void build(int fa, int &x, int l, int r)
  {
    if (l>r) return;
    int mid = l + r >> 1;
    x = Node(fa, dfs[mid]);
    if (dfs[mid] > 0) L[dfs[mid]] = x; else R[-dfs[mid]] = x;
    build(x, ch[x][0], l, mid - 1);
    build(x, ch[x][1], mid + 1, r);
  }
  void build()
  {
    Dfs(0);
    int root;
    for (int i = 0, j = 0, k = 0; i < dfs.size(); i++)
    {
      k += dfs[i]>0 ? 1 : -1;
      if (!k) build(0, root, j, i), j = i + 1;
    }
  }
  int find(int x)
  {
    Splay(L[x], 0);
    for (int i = L[x]; i; i = ch[i][0]) if (!ch[i][0]) { return A[i]; }
  }
  void remove(int x, int y)
  {
    if (x == y) return;
    int l = L[x], r = R[x];
    Splay(l, 0);  Splay(r, l);

    int ll = ch[l][0], rr = ch[r][1], z = 0;
    for (int i = ll; i; i = ch[i][1]) if (!ch[i][1]) { z = i; break; }
    ch[l][0] = ch[r][1] = 0;
    F[ll] = F[rr] = 0;
    if (z) ch[z][1] = rr; F[rr] = z;
    if (!y) return;
    if (find(y) == x) { ch[l][0] = ll;  ch[r][1] = rr; F[ll] = l; F[rr] = r; ch[z][1] = 0; return; }
    
    Splay(L[y], 0); for (int i = ch[L[y]][1]; i; i = ch[i][0]) if (!ch[i][0]) { Splay(i, L[y]); break; }
    ch[ch[L[y]][1]][0] = l; F[l] = ch[L[y]][1];
  }
}solve;


int main()
{
  int tt = 0;
  while (scanf("%d", &n) != EOF)
  {
    if (tt++) printf("\n");
    solve.clear();  dfs.clear();
    for (int i = 0; i <= n; i++) t[i].clear();
    for (int i = 1; i <= n; i++) Scan(x),t[x].push_back(i);
    solve.build();
    scanf("%d", &m);
    while (m--)
    {
      scanf("%s", s);
      if (s[0] == 'Q') Scan(x), printf("%d\n", solve.find(x));
      else Scan(l), Scan(r), solve.remove(l, r);
    }
  }
  return 0;
}

此題對于splay删除的處理有挺多坑的，調了好久終于算是理清楚了，一定要注意細節。。這兩個版本删除操作不同

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, m, l, r, L[maxn], R[maxn], x, root;
char s[20];
vector<int> t[maxn], dfs;

void Scan(int &x)
{
  char ch;
  while ((ch = getchar()) > '9' || ch < '0');
  int res = ch - '0';
  while ((ch = getchar()) <= '9'&&ch >= '0') res = res * 10 + ch - '0';
  x = res;
}

struct Splays
{
  const static int maxn = 2e5 + 10;     //節點個數
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右兒子，父親節點和節點總個數
  int A[maxn];
  int Node(int f, int a) { A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; 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]; 
    if (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;
  }
  void Splay(int x, int r)
  {
    while (F[x] != r)
    {
      if (F[F[x]] == r) { 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 Dfs(int x)
  {
    if (x) dfs.push_back(x);
    for (int i = 0; i < t[x].size(); i++) Dfs(t[x][i]);
    if (x) dfs.push_back(-x);
  }
  void build(int fa, int &x, int l, int r)
  {
    if (l>r) return;
    int mid = l + r >> 1;
    x = Node(fa, dfs[mid]);
    if (dfs[mid] > 0) L[dfs[mid]] = x; else R[-dfs[mid]] = x;
    build(x, ch[x][0], l, mid - 1);
    build(x, ch[x][1], mid + 1, r);
  }
  void build()
  {
    Dfs(0);
    int root;
    for (int i = 0, j = 0, k = 0; i < dfs.size(); i++)
    {
      k += dfs[i]>0 ? 1 : -1;
      if (!k) build(0, root, j, i), j = i + 1;
    }
  }
  int find(int x)
  {
    Splay(L[x], 0);
    for (int i = L[x]; i; i = ch[i][0]) if (!ch[i][0]) { return A[i]; }
  }
  void remove(int x, int y)
  {
    if (x == y) return;
    int l = L[x], r = R[x];
    Splay(l, 0);  Splay(r, l);

    int ll = ch[l][0], rr = ch[r][1], lr = 0, rl = 0;

    for (int i = ll; i; i = ch[i][1]) if (!ch[i][1]) { lr = i; break; }
    for (int i = rr; i; i = ch[i][0]) if (!ch[i][0]) { rl = i; break; }
    
    int g = l;
    if (lr) { Splay(lr, 0); Splay(rl, lr); g = ch[rl][0]; F[g] = ch[rl][0] = 0; }
    if (!y) return;
    if (find(y) == x){ Splay(g, 0); F[g] = rl;  ch[rl][0] = g; return; }
    Splay(L[y], 0); for (int i = ch[L[y]][1]; i; i = ch[i][0]) if (!ch[i][0]) { Splay(i, L[y]); break; }
    ch[ch[L[y]][1]][0] = g; F[g] = ch[L[y]][1];
  }
}solve;


int main()
{
  int tt = 0;
  while (scanf("%d", &n) != EOF)
  {
    if (tt++) printf("\n");
    solve.clear();  dfs.clear();
    for (int i = 0; i <= n; i++) t[i].clear();
    for (int i = 1; i <= n; i++) Scan(x),t[x].push_back(i);
    solve.build();
    scanf("%d", &m);
    while (m--)
    {
      scanf("%s", s);
      if (s[0] == 'Q') Scan(x), printf("%d\n", solve.find(x));
      else Scan(l), Scan(r), solve.remove(l, r);
    }
  }
  return 0;
}

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, m, l, r, L[maxn], R[maxn], x, root;
char s[20];

void Scan(int &x)
{
  char ch;
  while ((ch = getchar()) > '9' || ch < '0');
  int res = ch - '0';
  while ((ch = getchar()) <= '9'&&ch >= '0') res = res * 10 + ch - '0';
  x = res;
}

struct Splays
{
  const static int maxn = 2e5 + 10;     //節點個數
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右兒子，父親節點和節點總個數
  int A[maxn];
  int Node(int f, int a) { A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; 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];
    if (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;
  }
  void Splay(int x, int r)
  {
    while (F[x] != r)
    {
      if (F[F[x]] == r) { 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 x)
  {
    L[x] = Node(0, x);
    R[x] = ch[L[x]][1] = Node(L[x], x);
  }
  int find(int x)
  {
    Splay(L[x], 0);
    for (int i = L[x]; i; i = ch[i][0]) if (!ch[i][0]) { return A[i]; }
  }
  void remove(int x, int y)
  {
    if (x == y) return;
    int l = L[x], r = R[x];
    Splay(l, 0);  Splay(r, l);

    int ll = ch[l][0], rr = ch[r][1], lr = 0, rl = 0;

    for (int i = ll; i; i = ch[i][1]) if (!ch[i][1]) { lr = i; break; }
    for (int i = rr; i; i = ch[i][0]) if (!ch[i][0]) { rl = i; break; }

    int g = l;
    if (lr) { Splay(lr, 0); Splay(rl, lr); g = ch[rl][0]; F[g] = ch[rl][0] = 0; }
    if (!y) return;
    if (find(y) == x){ Splay(g, 0); F[g] = rl;  ch[rl][0] = g; return; }
    Splay(L[y], 0); for (int i = ch[L[y]][1]; i; i = ch[i][0]) if (!ch[i][0]) { Splay(i, L[y]); break; }
    ch[ch[L[y]][1]][0] = g; F[g] = ch[L[y]][1];
  }
}solve;


int main()
{
  int tt = 0;
  while (scanf("%d", &n) != EOF)
  {
    if (tt++) printf("\n");
    solve.clear();  
    for (int i = 1; i <= n; i++) solve.build(i);
    for (int i = 1; i <= n; i++) Scan(x), solve.remove(i, x);
    scanf("%d", &m);
    while (m--)
    {
      scanf("%s", s);
      if (s[0] == 'Q') Scan(x), printf("%d\n", solve.find(x));
      else Scan(l), Scan(r), solve.remove(l, r);
    }
  }
  return 0;
}

HDU 2475 Box

繼續閱讀

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

JAVA 系列——>開發工具IntelliJ IDEA的安裝以及配置、快捷鍵IDEA 簡介

UVA 519 Puzzle (II)

磁盤結構及在Linux中的命名

HDU5066-Harry And Physical Teacher Harry And Physical Teacher