[BZOJ 4448][SCOI 2015] 情报传递

题目大意

\(n\) 名特务,每个特务有一个上司(显然,有一个特务头子没有上司),每名特务只能与自己的上司与手下联系。每天有一个操作:

  • 搜集情报:从这一天开始,每天该特务的危险值加 \(1\),在当天,其危险值仍为 \(0\)
  • 传递情报:询问两个特务的联系路线上的所有特务有多少个,以及有多少个的危险值大于 \(c\)

\(1 \leqslant n, \; q \leqslant 200,000\)

题目链接

BZOJ 4448

题解

显然,特务构成一个树形结构。

对于每一个询问,求两点间路径上的点数比较简单。

对于第二问,第 \(i\) 天的询问只受在第 \(i - c\) 天以前的操作影响。对于每天的操作,定义 \(c'\),当是修改(搜集情报)时,为天数;是询问时,为 \(天数 - c\)。以 \(c'\) 对操作排序(相同时,由于修改对当天不产生影响,询问在前),对每一个修改,在 LCT 上为节点加 \(1\);对于询问,为路径上节点权值和。

(这题树剖显然也可以做)

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 200005;
const int MAXQ = 200005;
struct LinkCurTree {
struct Node {
Node *c[2], *fa, *pathFa;
int w, sum, size;
bool rev;
Node() : fa(NULL), pathFa(NULL), w(0), sum(0), size(0), rev(false) {
c[0] = c[1] = NULL;
}
void pushDown() {
if (rev) {
std::swap(c[0], c[1]);
if (c[0]) c[0]->rev ^= 1;
if (c[1]) c[1]->rev ^= 1;
rev = false;
}
}
void maintain() {
sum = (c[0] ? c[0]->sum : 0) + (c[1] ? c[1]->sum : 0) + w;
size = (c[0] ? c[0]->size : 0) + (c[1] ? c[1]->size : 0) + 1;
}
int relation() {
return fa->c[1] == this;
}
void rotate() {
std::swap(pathFa, fa->pathFa);
int x = relation();
Node *o = fa;
fa = o->fa;
if (fa) fa->c[o->relation()] = this;
o->c[x] = c[x ^ 1];
if (c[x ^ 1]) c[x ^ 1]->fa = o;
c[x ^ 1] = o;
o->fa = this;
o->maintain(), maintain();
}
void splay() {
while (fa) {
if (fa->fa) fa->fa->pushDown();
fa->pushDown(), pushDown();
if (!fa->fa) rotate();
else if (fa->relation() == relation()) fa->rotate(), rotate();
else rotate(), rotate();
}
pushDown();
}
void expose() {
splay();
if (c[1]) {
std::swap(c[1]->fa, c[1]->pathFa);
c[1] = NULL;
maintain();
}
}
bool splice() {
splay();
if (!pathFa) return false;
pathFa->expose();
pathFa->c[1] = this;
pathFa->maintain();
std::swap(fa, pathFa);
return true;
}
void access() {
expose();
while (splice());
}
void evert() {
access();
splay();
rev ^= 1;
}
} N[MAXN];
void link(int u, int v) {
N[v].evert();
N[v].pathFa = &N[u];
}
void update(int u, int w) {
N[u].splay();
N[u].w = w;
N[u].maintain();
}
void query(int u, int v, int &size, int &sum) {
N[u].evert();
N[v].access();
N[v].splay();
size = N[v].size;
sum = N[v].sum;
}
} lct;
struct Query {
int op, u, v, c, *dist, *cnt;
bool operator<(const Query &another) const {
return c < another.c || (c == another.c && op < another.op);
}
#ifdef DBG
void print() const {
printf("Query[op = %d, u = %d, v = %d, c = %d]\n", op, u, v, c);
}
#endif
} Q[MAXQ];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int fa;
scanf("%d", &fa);
if (fa) lct.link(fa, i);
}
int q;
scanf("%d", &q);
static int ans[MAXQ][3];
for (int i = 0; i < q; i++) {
scanf("%d", &Q[i].op);
if (Q[i].op == 2) scanf("%d", &Q[i].u), Q[i].c = i;
else {
int c;
scanf("%d %d %d", &Q[i].u, &Q[i].v, &c);
Q[i].c = i - c;
}
ans[i][0] = Q[i].op;
Q[i].dist = &ans[i][1];
Q[i].cnt = &ans[i][2];
}
std::sort(Q, Q + q);
for (int i = 0; i < q; i++) {
#ifdef DBG
printf("i = %d, ", i);
Q[i].print();
#endif
if (Q[i].op == 2) lct.update(Q[i].u, 1);
else {
int dist, cnt;
lct.query(Q[i].u, Q[i].v, dist, cnt);
*Q[i].dist = dist;
*Q[i].cnt = cnt;
#ifdef DBG
printf("dist = %d, cnt = %d\n", dist, cnt);
#endif
}
}
for (int i = 0; i < q; i++) if (ans[i][0] == 1) printf("%d %d\n", ans[i][1], ans[i][2]);
return 0;
}