CF1109F 题解
__vector__
·
·
题解
第一道自己想出做法的 CF Div.1 F，记录一下它的两种维护方式。
问题转化
求有多少个点对 $(l,r)$ 满足 $1 \le l \le r \le n$，使得 $[l,r]$ 中的点构成的导出子图是一棵树。
### 考虑合法条件。
1. 不能存在环。
2. 边数等于点数减一。
考虑编号升序枚举右端点，想一想哪些左端点是符合要求的。
- 仅考虑条件一
注意到，如果 $[l,r]$ 合法，那么 $r \ge \forall l' \gt l$，$[l',r]$ 是合法的。在右端点递增的情况下，最小的符合要求的左端点是单调不降的。
基于此性质，可以双指针。右端每新增一个点，就需要从左端弹出若干个点，使得加上新的边后不会形成环，此过程可以 LCT 维护。
整体二分同样可以完成任务。
至此，求出了每个右端点对应哪些符合条件一的左端点。
- 考虑条件二
考虑对每个点维护一个权值，代表其作为左端点时，总点数减去边数是多少。
枚举右端点的时候使用线段树动态更新就可以。
注意到对于符合条件一的左端点，其权值必然大于等于 $1$，问题可以转化为求最小值及其出现次数。
虽然 LCT 常数巨大，但是在这道题可以吊打普通的整体二分。
其中 LCT 维护的时间复杂度是 $O(nm \log nm)$，整体二分多一个并查集的复杂度。
[LCT submission](https://codeforces.com/contest/1109/submission/303456762)，[整体二分 submission](https://codeforces.com/contest/1109/submission/304031080)。