Chro's Blog


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


「BZOJ 4012」「HNOI2015」开店

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

Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n 个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 u(u为编号),然后在 u开一家面向年龄在 L到R 之间(即年龄大于等于 L、小于等于 R)的妖怪的店。也有可能 u这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪,到点 u 的距离的和是多少(妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Input

第一行三个用空格分开的数 n、Q和A,表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行n个用空格分开的数 x_1、x_2、…、x_n,x_i 表示第i 个地点妖怪的年龄,满足0<=x_i<A。(年龄是可以为 0的,例如刚出生的妖怪的年龄为 0。)

接下来 n-1 行,每行三个用空格分开的数 a、b、c,表示树上的顶点 a 和 b 之间有一条权为c(1 <= c <= 1000)的边,a和b 是顶点编号。

接下来Q行,每行三个用空格分开的数 u、 a、 b。对于这 Q行的每一行,用 a、b、A计算出 L和R,表示询问“在地方 u开店,面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行,L 和 R 的计算方法为:L=min(a%A,b%A),R=max(a%A,b%A)。对于第 2到第 Q行,假设前一行得到的方便值为 ans,那么当前行的 L 和 R 计算方法为: L=min((a+ans)%A,(b+ans)%A),R=max((a+ans)%A,(b+ans)%A)。

Output

对于每个方案,输出一行表示方便值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4

Sample Output

1
2
3
4
5
6
7
8
9
10
1603
957
7161
9466
3232
5223
1879
1669
1282
0

HINT

满足 n<=150000,Q<=200000。对于所有数据,满足 A<=10^9

Solution

据说这题可以用动态点分治,然而我不会。(马上 NOI 了还是不要学新算法了好吧?)


我们知道,对于一对节点 (u, v) 及其 LCA(o),总是有 dis(u, v)=dis(u, root)+dis(v, root)-2*dis(o, root)。

对于本题的单次询问而言,该次询问中所有节点对 (i, x) 都有一个固定终点 x。而如果我们把所有妖怪按年龄离散化,那么前两个加数都可以在预处理后单次 $O(\log_2n)$ 算出来。

所以重点在于如何维护所有 LCA 到根的距离之和。还是按照年龄离散化,依次处理每个妖怪,该妖怪到根节点路径上的每条边记录一个「+1」,代表该边被 1 个妖怪经过 1 次。从询问节点 x 向根走,经过的每条边的标记乘以该边的长度之和即为答案。

我们可以用树链剖分来快速地修改路径标记,用线段树维护若干边上「标记 * 长度」之和。由于多次在线区间询问,这里要用主席树(而不是普通的线段树)。

代码比较长,细节较多,不过没有耗费我太多时间(仅在开始时把数组开小导致一次 RE)。

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
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define lc(o) (t[o].lc)
#define rc(o) (t[o].rc)
#define mid ((l + r) >> 1)
const int maxn = 150005;
const int maxlogn = 41;
struct edge { int to, next, val; } e[maxn << 1];
struct node {
int lc, rc, tag;
long sum;
} t[maxn * maxlogn];
int n, q, A, age[maxn], disc[maxn], id[maxn], pos[maxn];
int tot, head[maxn], tcnt, par[maxn];
int root[maxn], son[maxn], size[maxn], dfn[maxn], top[maxn], dfsc;
long val[maxn], dis[maxn], dis2[maxn], ans = 0;
long val_sum(int l, int r) { return val[r] - val[l - 1]; }
long dis_sum(int l, int r) { return dis2[r] - dis2[l - 1]; }
int update(int o, int l, int r, int ql, int qr, int v) {
int e = ++tcnt;
t[e] = t[o];
if (ql <= l && r <= qr) {
t[e].tag += v;
t[e].sum += v * val_sum(l, r);
} else {
if (ql <= mid) lc(e) = update(lc(o), l, mid, ql, qr, v);
if (mid < qr) rc(e) = update(rc(o), mid + 1, r, ql, qr, v);
t[e].sum = t[lc(e)].sum + t[rc(e)].sum + t[e].tag * val_sum(l, r);
}
return e;
}
long query(int o, int l, int r, int ql, int qr, long add = 0) {
if (ql <= l && r <= qr) return t[o].sum + add * val_sum(l, r);
long ans = 0;
if (ql <= mid) ans += query(lc(o), l, mid, ql, qr, add + t[o].tag);
if (mid < qr) ans += query(rc(o), mid + 1, r, ql, qr, add + t[o].tag);
return ans;
}
void update(int &o, int u) {
while (u) {
o = update(o, 1, n, dfn[top[u]], dfn[u], 1);
u = par[top[u]];
}
}
long query(int x, int y, int u) {
long ans = 0;
while (u) {
ans += query(y, 1, n, dfn[top[u]], dfn[u]) - query(x, 1, n, dfn[top[u]], dfn[u]);
u = par[top[u]];
}
return ans;
}
void dfs1(int u, int p) {
size[u] = 1;
for (int t = head[u]; t; t = e[t].next) {
int v = e[t].to;
if (v == p) continue;
par[v] = u;
dis[v] = dis[u] + e[t].val;
dfs1(v, u);
size[u] += size[v];
if (size[v] >= size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int p) {
dfn[u] = ++dfsc;
val[dfsc] = dis[u] - dis[p];
top[u] = u == son[p] ? top[p] : u;
if (son[u]) dfs2(son[u], u);
for (int t = head[u]; t; t = e[t].next) {
int v = e[t].to;
if (v == p || v == son[u]) continue;
dfs2(v, u);
}
}
void arc(int f, int t, int v) {
e[++tot] = (edge){t, head[f], v}, head[f] = tot;
e[++tot] = (edge){f, head[t], v}, head[t] = tot;
}
bool cmp_age(int a, int b) { return age[a] < age[b]; }
int main() {
scanf("%d%d%d", &n, &q, &A);
for (int i = 1; i <= n; ++i) scanf("%d", age + i), disc[i] = age[i], id[i] = i;
sort(disc + 1, disc + n + 1);
for (int i = 1; i <= n; ++i) age[i] = lower_bound(disc + 1, disc + n + 1, age[i]) - disc;
sort(id + 1, id + n + 1, cmp_age);
for (int i = 1; i <= n; ++i) pos[id[i]] = i;
for (int i = 1, a, b, c; i < n; ++i) scanf("%d%d%d", &a, &b, &c), arc(a, b, c);
dfs1(1, 0), dfs2(1, 0);
for (int i = 2; i <= n; ++i) val[i] += val[i - 1];
for (int i = 1; i <= n; ++i) dis2[i] = dis2[i - 1] + dis[id[i]];
for (int i = 1; i <= n; ++i) update(root[i] = root[i - 1], id[i]);
for (int i = 1, u, a, b; i <= q; ++i) {
scanf("%d%d%d", &u, &a, &b);
int L = (a + ans) % A, R = (b + ans) % A;
if (L > R) swap(L, R);
int x = lower_bound(disc + 1, disc + n + 1, L) - disc;
int y = upper_bound(disc + 1, disc + n + 1, R) - disc - 1;
ans = query(root[x - 1], root[y], u) * -2ll;
ans += (y - x + 1) * dis_sum(pos[u], pos[u]);
ans += dis_sum(x, y);
printf("%lld\n", ans);
}
return 0;
}
最近的文章

「BZOJ 4200」「UOJ 132」「NOI2015」小园丁与老司机

小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有 n 棵许愿树,编号 1,2,3,…,n,每棵树可以看作平面上的一个点,其中第 i 棵树 (1≤i≤n) 位于坐标 (xi,yi)。任意两棵树的坐标均不相同。 老司机 Mr. P 从原点 (0,0) 驾车出发,进行若干轮行动。每…

BZOJ, UOJ, 上下界最小流, 动态规划, 网络流 继续阅读
更早的文章

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

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

BZOJ, UOJ, 决策单调性, 动态规划 继续阅读