题目链接

题意:求区间图字典序最小的最大点独立集


先去重。

显然第一问直接贪心即可,对于第二问,这种限定字典序的问题常常按顺序钦定,然后判定是否合法。

那么我们需要维护这么个东西,插入一个区间后,把一个可用的区间分割成了三部分,其中如果左右拼起来再+1(中间部分)等于原来这个可用区间能放的区间个数,则钦定这个区间不影响答案。

现在需要快速求出一个区间最多能放多少个区间,可以预处理一个区间开始往右放 i 个区间最近能放到哪里,显然可以倍增加速。

 


一个非常弱的准退役OIER