Chro's Blog

だから 迷わない 頑張ろう

Those things that hurt, instruct.


「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, 决策单调性, 动态规划 继续阅读