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
1
1
2
1
1
树形转线形，巧妙的利用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;
}