Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 2759」一个动态树好题

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

有N个未知数x[1..n]和N个等式组成的同余方程组:

x[i]=k[i]*x[p[i]]+b[i] mod 10007

其中,k[i],b[i],x[i]∈[0,10007)∩Z

你要应付Q个事务,每个是两种情况之一:

一.询问当前x[a]的解

A a

无解输出-1

x[a]有多解输出-2

否则输出x[a]

二.修改一个等式

C a k[a] p[a] b[a]

Input

N

下面N行,每行三个整数k[i] p[i] b[i]

Q

下面Q行,每行一个事务,格式见题目描述

Output

对每个询问,输出一行一个整数。

对100%的数据,1≤N≤30000,0≤Q≤100000,时限2秒,其中询问事务约占总数的80%

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5

Sample Output

1
2
3
4
4276
7141
4256
2126

Solution

Link-Cut Cactus?! 当然本题没必要搞的那么麻烦(我也不会写啊 qwq)

注意到每个 i 和 p[i] 之间的边形成了一个基环树森林。那么我们可以拆掉一条边把它变成普通的树,用 LCT 来维护。在拆掉的边的两个节点 u→p[u] 中,选择 u 作为树的根,并额外开一个域记录它到节点 p[u] 有一条成环的边。

每个节点记录它的 k, b,这是一个线性函数的形式。同时维护「如果按照树链的顺序依次执行每个变换,它等价于什么线性函数」。

也就是说如果用 $f_u(x)$ 表示以 u 为根的子树的「组合线性函数」、$g_u(x)$ 表示 u 节点本身记录的函数,那么维护 Splay 上的节点时, $f_u(x)=f_{u.lc}(g_u(f_{u.rc}(x)))$

回答查询时,首先确定被根指向的节点的值(可以列出一个线性模方程,然后分类讨论),如果该值唯一,再代入询问节点。

修改操作时,先删边再加边。需要讨论该边是否为成环的「特殊边」。

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
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
const int maxn = 30005;
struct func {
int k, b;
func operator()(func r) { return (func){k * r.k % mod, (k * r.b % mod + b % mod) % mod}; }
int operator()(int x) { return (k * x % mod + b) % mod; }
} unit = (func){1, 0};
struct bst {
bst *ch[2], *par, *sp;
func val, cum;
int flip;
void maintain() { cum = ch[1]->cum(this->val(ch[0]->cum)); }
void pushdown(bool = false);
bool isroot();
} *id[maxn], *null;
int n, p[maxn];
void rotate(bst *o, int d) {
bst *k = o->ch[!d];
o->ch[!d] = k->ch[d];
o->ch[!d]->par = o;
k->ch[d] = o;
k->par = o->par;
if (o->par->ch[0] == o) o->par->ch[0] = k;
else if (o->par->ch[1] == o) o->par->ch[1] = k;
o->par = k;
o->maintain();
}
void splay(bst *o) {
o->pushdown(true);
while (!o->isroot()) {
bst *y = o->par, *z = y->par;
int d = o == y->ch[0] ? 1 : 0;
if (z->ch[!d] == y) rotate(z, d);
rotate(y, d);
}
o->maintain();
}
void access(bst *o) {
bst *tmp = null;
while (o != null) {
splay(o);
o->ch[1] = tmp;
o->maintain();
tmp = o;
o = o->par;
}
}
void evert(bst *o) {
access(o);
splay(o);
o->flip ^= 1;
}
bst *getroot(bst *o) {
access(o);
splay(o);
while (o->ch[0] != null) o = o->ch[0];
return o;
}
bst *newnode(func f) {
bst *o = new bst;
o->ch[0] = o->ch[1] = o->par = o->sp = null;
o->val = o->cum = f;
o->flip = false;
return o;
}
bool bst::isroot() { return par->ch[0] != this && par->ch[1] != this; }
void bst::pushdown(bool p) {
if (p && !isroot()) par->pushdown();
if (flip) {
flip = 0;
swap(ch[0], ch[1]);
if (ch[0] != null) ch[0]->flip ^= 1;
if (ch[1] != null) ch[1]->flip ^= 1;
}
}
void init() {
null = new bst;
null->par = null->ch[0] = null->ch[1] = null->sp = null;
null->val = null->cum = unit;
null->flip = 0;
}
void input() {
scanf("%d", &n);
for (int i = 1, k, b; i <= n; ++i) {
scanf("%d%d%d", &k, p + i, &b);
id[i] = newnode((func){k, b});
}
for (int u = 1; u <= n; ++u) {
int v = p[u];
if (getroot(id[u]) == getroot(id[v])) id[u]->sp = id[v];
else id[u]->par = id[v];
}
}
int inv(int x) {
int ans = 1;
for (int b = mod - 2; b; b >>= 1) {
if (b & 1) (ans *= x) %= mod;
(x *= x) %= mod;
}
return ans;
}
int query(bst *o) {
bst *u = getroot(o), *v = u->sp;
access(v), splay(v);
int k = v->cum.k, b = v->cum.b;
if (k == 1) return b ? -1 : -2;
int x = b * inv((mod + 1 - k) % mod) % mod;
access(o), splay(o);
return o->cum(x);
}
void modify(bst *o, int k, bst *p, int b) {
o->val = (func){k, b};
o->maintain();
bst *r = getroot(o);
if (r == o) o->sp = null;
else {
access(o), splay(o);
o->ch[0] = o->ch[0]->par = null;
o->maintain();
if (getroot(r->sp) != r) {
access(r), splay(r);
r->par = r->sp;
r->sp = null;
}
}
access(o), splay(o);
if (getroot(p) == o) o->sp = p;
else o->par = p;
}
void solve() {
int q;
scanf("%d", &q);
while (q--) {
char t[5];
int a, b, c, d;
scanf("%s", t);
if (*t == 'A') {
scanf("%d", &a);
printf("%d\n", query(id[a]));
} else {
scanf("%d%d%d%d", &a, &b, &c, &d);
modify(id[a], b, id[c], d);
}
}
}
int main() {
init();
input();
solve();
return 0;
}
最近的文章

「BZOJ 4654」「UOJ 223」「NOI2016」国王饮水记

Description跳蚤国有 n 个城市,伟大的跳蚤国王居住在跳蚤国首都中,即 1 号城市中。跳蚤国最大的问题就是饮水问题,由于首都中居住的跳蚤实在太多,跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用,这导致跳蚤国王也经常喝不上水。于是,跳蚤国在每个城市都修建了一个圆柱形水箱,这些水箱完全相同且…

BZOJ, UOJ, 决策单调性, 动态规划 继续阅读
更早的文章

「BZOJ 2306」「CTSC2011」幸福路径

Description有向图 G有n个顶点 1, 2, …, n,点i 的权值为 w(i)。现在有一只蚂蚁,从给定的起点 v0出发,沿着图 G 的边爬行。开始时,它的体力为 1。每爬过一条边,它的体力都会下降为原来的 ρ 倍,其中ρ 是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度,是它…

BZOJ, Floyd, 倍增 继续阅读