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

### 传送门

“_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);
}
}