【线段树】区间不重复覆盖

传送门

题目意思是依次给n个区间,长度为1或者2,让从里面选一些区间,使得1到m都被覆盖。并且选出区间的编号差要最小。

用双指针求取最短编号差。

难点在于怎么动态确定区间是否被覆盖了。

对于一个点,可能被三种区间覆盖,于是我们对于区间的端点进行分类。用_表示可以被填的方块类型。

“_LR” 代表区间左端点可以填为长度为1或者2的右端点,但右端点不超出。即可能向左超出
“LR_” 代表区间右端点可以填为长度为1或者2的左端点,但左端点不超出。即可能向右超出
“_LR_” 代表左右端点都有可能超出。
“L_R” 代表左右端点都不超出。

然后用线段树维护这四个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 23;
struct Node{
    int l, r;
    int s, sl, sr, sn, lv, rv;
}tr[maxn * 4];
void pushup(Node &u, Node &l, Node &r)
{
    u.lv = l.lv;
    u.rv = r.rv;
    int mv = l.rv & (1 << 1);
    u.s = (l.s && r.s) || (l.sl && r.sr && mv);
    u.sl = (l.s && r.sl) || (l.sl 
Read the rest