传送门

题目意思是依次给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 && r.sn && mv);
    u.sr = (r.s && l.sr) || (r.sr && l.sn && mv);
    u.sn = (l.sr && r.sl) || (l.sn && r.sn && mv);
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, 0, 1, 1, 0, 0, 0};
    else 
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int p, int v)
{
    if(tr[u].l == tr[u].r && tr[u].l == p) 
    {
        tr[u].lv ^= v; tr[u].rv ^= v;
        if(v == 1) tr[u].s ^= 1;
    }
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(p <= mid) modify(u << 1, p, v);
        else modify(u << 1 | 1, p, v);
        pushup(u);
    }
}
pair<int,int> back[maxn * 10];
int main()
{
    int T; scanf("%d", &T);
    int n = 0, m = 0, l = 0, r = 0;
    while(T--)
    {
        scanf("%d%d", &n, &m);
        build(1, 1, m);
        int ans = 0x3f3f3f3f;
        for(int i = 1, j = 1; i <= n; i++) 
        {
            scanf("%d%d", &l, &r);
            if(l == r) back[i] = {l, 1};
            else back[i] = {l, 1 << 1};
            modify(1, back[i].first, back[i].second);
            while(tr[1].s) 
            {
                ans = min(ans, i - j + 1);
                modify(1, back[j].first, back[j].second);
                j++;
            }
        }
        if(ans > n) ans = -1;
        printf("%d\n", ans);
    }
}