关于 Milk Visits 的近10条评论(全部评论)
事实上也可以这样：记录 $pre_c$ 表示 $c$ 最后一次出现的位置。扫描线，扫到询问 $(l, r, c)$ 的时候只需判断是否有 $pre_c\ge l$ 即可。这样的复杂度仍然是 $\mathcal O(m\log n)$。 yrtiop 2024-04-03 12:36 3楼
本人做法:树链剖分+主席树 $O(nlog^2n)$ 还有其他做法: ·树剖+线段树+平衡树(树套树套树? Orz) $O(nlog^3n)$ ·dfs+主席树 $O(nlogn)$ ·树剖+分块 $O(n\sqrt{n}log(n\sqrt{n}))$ 都不会捏┭┮﹏┭┮ ┭┮﹏┭┮ 2023-12-13 21:39 2楼
写完此题受益良多啊，在这里写个小总结吧。。。 1.算是复习了一边树剖（是的我没写主席树，这就是吸氧也不如一只log的主席树快的原因。。。）虽然在跳链时写错了一点。。。 2.学到了新的判断数是否在区间的方法。。 3.使用了毒瘤的新码风。。 4.对迭代器有了较浅的理解。。 5.%%%%%%%%%hs大佬 ShallowDream雨梨 2019-12-29 20:45 1楼

3320. [USACO19 DEC Gold]Milk Visits

★★★☆ 输入文件：_milkvisits.in 输出文件：_milkvisits.out 简单对比
时间限制：1 s 内存限制：256 MiB

Farmer John 计划建造N（1≤N≤10^5）个农场，用N−1 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为1 到N 之间的一个整数Ti。

Farmer John 的M 个朋友（1≤M≤10^5）经常前来拜访他。在朋友i 拜访之时，Farmer John 会与他的朋友沿着从农场Ai 到农场Bi 之间的唯一路径行走（可能有 Ai=Bi）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于

Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer

John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入的第一行包含两个整数N 和M。

第二行包含N 个空格分隔的整数 T1,T2,…,TN。第i 个农场内的奶牛的品种用Ti 表示。

以下N−1 行，每行包含两个不同的整数X 和Y（1≤X,Y≤N），表示农场X 与Y 之间有一条边。

以下M 行，每行包含整数Ai，Bi，以及Ci。Ai 和Bi 表示朋友i 拜访时行走的路径的端点，Ci（1≤Ci≤N）表示这个朋友喜欢的牛奶的奶牛品种。

输出一个长为M 的二进制字符串。如果第i 个朋友会感到高兴，则字符串的第i个字符为 '1'否则为 '0'。

5 5

1 1 2 1 2

1 2

2 3

2 4

1 5

1 4 1

1 4 2

1 3 2

1 3 1

5 5 1

在这个样例中，从农场 1 到农场 4 的路径包括农场 1、2 和 4。这些农场中都是品种 1 的奶牛，所以第一个朋友会感到满意，而第二个朋友不会。

测试点性质：

测试点 2 为以下第二个样例。

测试点 3 满足 N≤10^3,M≤2*10^3。

测试点 4-7 满足Ci≤10（Ci定义见下）。

在此键入。