F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register |
---|
Problem 5331 >> 第二问也可以用莫队 |
save_code @ 2018-06-14 09:33:06
不过维护参数很麻烦
第二问的 答案 等于 总数 减去 枚举 每个颜色, 这条链上所有不包含 这个颜色的和 我们可以 dp[id]记录 id 到根节点 不满足条件的答案 (也就是 相同两个颜色 之间距离减 1的组合数和) A,B 这条链的 反面结果 就等于 dp[lca]+ 每种 颜色 三个关键点的 情况 比如 a,b,c 就是(dist[b]-dist[a]-1)*(dist[c]-dist[a]-1) a表示 改颜色 在 A到lca之间 离lca最近的 点,b表示 该颜色在 B到lca之间 离lca最近的点,c表示 lca到根节点 之间离 lca最近的点, 然后 莫队算法维护这三个点 以及 一系列(一坨)参数 反正 目测应该是可以实现的,只不过 很麻烦,很纠结。。 复杂度n*sqrtn |
save_code @ 2018-06-14 09:35:15
统计 总数貌似也是一件麻烦的事情 啊
|
save_code @ 2018-06-14 09:46:00
还有主要麻烦点 在于 A到LCA 之间 不存在 某种颜色和B到LCA之间 不存在某种颜色,要维护一个 二元二次多项式, x,y 分别对应查询的 dist[a] 和dist[b]
|
nzhtl1477 @ 2018-06-14 16:16:43
是可以吧
|
save_code @ 2018-06-14 16:17:19
我觉得 用我的对颜色分块 实现起来 更简单一些啊 虽然多个根号log
|
save_code @ 2018-06-17 03:51:25
600多行终于过了啊。。。。
数据都没有 颜色个数>=sqrt(n)的情况 直接用算法2就能AC... |
nzhtl1477 @ 2018-06-17 14:27:20
orz 600行
|
save_code @ 2018-06-17 14:59:34
很显然 status 有 3000+K的, 明显我做复杂了啊
|
nzhtl1477 @ 2018-06-17 17:07:52
肯定
(话说您的代码一直都很长耶) |
save_code @ 2018-06-17 17:09:52
最长的貌似是 uoj 90 26K+
|
save_code @ 2018-06-17 17:10:27
那道题 论文的方法没有见过啊。。。。自己自创解法
|
nzhtl1477 @ 2018-06-18 14:04:10
orz
|
Claris @ 2018-06-18 15:09:43
标算是利用数据随机性O(nlogn)做的。
|
iloi @ 2018-06-19 08:02:46
orz
|