面向对象程序设计(可持久化数组)

描述

传送门:2018 年 “游族杯” 上海市高校程序设计邀请赛暨华东师范大学第十届程序设计竞赛 - Problem C

在面向对象程序设计中,常常会运用到函数的扩展与重写。当一个类继承某个类的时候,它可以调用所有父类可以调用的函数。它可以声明新的函数。当新的函数签名与父类的某个函数一致时,就会发生函数的覆盖(重写)。所以,在子类的实例调用某个函数时,它会调用最近的父类(有可能是它自己)的那个函数实现。

这里我们不考虑访问权限等情况,我们只关心某个类在调用某个函数时,这个函数是在哪个类中实现的。

Input

输入具有如下格式:
$n \\
p_2 \ p_3 \ \ldots \ p_n \\
t_1 \ a_{11} \ a_{12} \ \ldots \ a_{1t_1} \\
t_2 \ a_{21} \ a_{22} \ \ldots \ a_{2t_2} \\
\vdots \\
t_n \ a_{n1} \ a_{n2} \ \ldots \ a_{nt_n} \\
q \\
u_1 \ r_1 \\
u_2 \ r_2 \\
\vdots \\
u_q \ r_q$

解释与数据规模约定:

  • $n$ 表示有 $n$ 个类,这些类从 $1$ 到 $n$ 编号。$2 ≤ n ≤ 10^5$。
  • $p_i$ 表示第 $i$ 个类的父类编号。$1 ≤ p_i ≤ i-1$。第 $1$ 个类是所有类共同的祖先类,这个类没有父类。
  • $t_i$ 表示在第 $i$ 个类中定义了多少个函数,$a_{i1}, a_{i2}, \ldots, a_{it_i}$ 表示第 $i$ 个类中的函数列表。同一个类的函数列表中不会出现两个相同的函数。$1 \le a_{ij} \le 10^6$。$0 \le t_i \le 10^6, \sum t_i \le 10^6$。
  • $q$ 表示询问个数。$1 ≤ q ≤ 10^5$。
  • $u_i,r_i$ 表示第 $i$ 个询问,询问第 $u_i$ 个类的实例在调用 $r_i$ 函数时,调用的是哪个类中的版本。$1 \le u_i \le n, 1 \le r_i \le 10^6$。

Output

对于每个询问,输出答案。如果调用不合法(会导致编译错误),输出 $-1$。

Examples

  • Input
1
2
3
4
5
6
7
8
9
10
11
12
5
1 2 3 3
2 2 1
0
2 5 2
2 4 5
1 5
4
3 4
5 2
4 5
1 3
  • Output
1
2
3
4
-1
3
4
-1

Note

样例等价于下面的 Java 代码。

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
class Class1 {
void function2() { System.out.println("1"); }
void function1() { System.out.println("1"); }
}

class Class2 extends Class1 {

}

class Class3 extends Class2 {
void function5() { System.out.println("3"); }
void function2() { System.out.println("3"); }
}

class Class4 extends Class3 {
void function4() { System.out.println("4"); }
void function5() { System.out.println("4"); }
}

class Class5 extends Class3 {
void function5() { System.out.println("5"); }
}

void test() {
new Class3().function4();
new Class5().function2();
new Class4().function5();
new Class1().function3();
}

思路

  • 好像大家都是离线的啊!比赛的时候觉得离线太难写了(是我太菜了),就写了个在线的做法QAQ
  • 对树上的每个结点建一个大小为$10^6$的数组,维护当前结点中每个函数的版本,没有提到的函数版本信息全部从父亲结点继承,提到的函数则进行覆盖。
  • 当然直接开数组是开不下的,但是注意到每个结点之间相同的信息较多,所以可以将数组可持久化。把可持久化线段树当数组用就可以了?

代码

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
#include <bits/stdc++.h>

const int N = 1 << 20;
int p[N];
int lson[N << 5], rson[N << 5], val[N << 5];
int rt[N];
int tot = 0;
void update(int p, int v, int l, int r, int o, int& x)
{
x = ++tot, lson[x] = lson[o], rson[x] = rson[o];
if(l == r)
{
val[x] = v;
// cout << x << " " << v << endl;
return;
}
int m = l + r >> 1;
if (p <= m) update(p, v, l, m, lson[o], lson[x]);
else update(p, v, m + 1, r, rson[o], rson[x]);
}
int query(int p, int l, int r, int o)
{
if(!o) return 0;
if(l == r) return val[o];
int m = l + r >> 1;
if (p <= m) return query(p, l, m, lson[o]);
else return query(p, m + 1, r, rson[o]);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif // ONLINE_JUDGE
fastin
int n;
cin >> n;
for (int i = 2; i <= n; i++) cin >> p[i];
for (int i = 1, t; i <= n; i++)
{
rt[i] = rt[p[i]];
cin >> t;
for (int j = 0, a; j < t; j++)
{
cin >> a;
update(a, i, 1, N, rt[i], rt[i]);
}
}
int q;
cin >> q;
while(q--)
{
static int u, r;
cin >> u >> r;
int ans = query(r, 1, N, rt[u]);
if (ans == 0) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}
捐助作者
0%