CF1109F Sasha and Algorithm of Silence's Sounds

发表于 分类于 ， ， 阅读次数：

题意：给出一个 的网格图，问有多少个编号区间的点集形成一棵树。

，时限 。

一个点集成为为树的充要条件：

  • 内部无环

  • 点数 = 边数 -1

序列扫描线，每次向右移动右端点 ，维护每个左端点的贡献。

对于内部无环这个要求，区间越长越可能违反，不难使用 配合 求出限制范围。

对于点边数要求，则使用线段树维护。

假如一个新点 时，若有边 ，则左端点 的区间 能够包含这条边。

于是， 的边数加一。

维护点数减边数，统计 (最小值) 的个数即可。

注意，双指针判边界的时候要格外注意，否则可能 WA#54 或者其他地方。

好像不是网格图也能做……