「LOJ6119」「2017 山东二轮集训 Day7」国王-点分治

发布于 2018-10-03  98 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「LOJ6119」「2017 山东二轮集训 Day7」国王-点分治

Description

在某个神奇的大陆上,有一个国家,这片大陆的所有城市间的道路网可以看做是一棵树,每个城市要么是工业城市,要么是农业城市,这个国家的人认为一条路径是 exciting 的,当且仅当这条路径上的工业城市和农业城市数目相等。现在国王想把城市分给他的两个儿子,大儿子想知道,他选择一段标号连续的城市作为自己的领地,并把剩下的给弟弟,能够满足两端都是自己城市的 exciting 路径比两端都是弟弟的城市的 exciting 路径数目多的方案数。

\(n\leqslant 10^5\)

Solution

首先可以发现如果限定了右端点,那么左端点的可取范围是以1开头的一段区间,且右端点单调不降。

设\(A\)表示两端点都在区间\([l,r]\)内的路径条数,\(B\)表示两端点都在区间外的路径条数,\(C\)表示一端点在区间内一端点在区间外的路径条数,\(S\)表示总路径条数\(\times 2\)

那么\(A>B \Leftrightarrow 2A+C>2B+C \Leftrightarrow 2A+C>S-2A-C\)

设\(f_i\)表示以\(i\)为端点的路径条数,点分治统计即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「LOJ6119」「2017 山东二轮集训 Day7」国王-点分治


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!