| by XianKa | No comments

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

传送门

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

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

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

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

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

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

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
struct Node{
    int _lr, lr_, l_r, _lr_;
}tr[maxn << 2];
int c1[maxn], c2[maxn];
void maintain(int rt, int l, int r)
{
    if(l == r)
    {
        tr[rt].l_r = c1[l];
        tr[rt].lr_ = tr[rt]._lr = 1;
        tr[rt]._lr_ = 0;
    }
    else 
    {
        int mid = (l + r) >> 1;
        tr[rt].l_r = ((tr[rt << 1].l_r && tr[rt << 1 | 1].l_r) || (tr[rt << 1].lr_ && tr[rt << 1 | 1]._lr && c2[mid]));
        tr[rt].lr_ = ((tr[rt << 1].l_r && tr[rt << 1 | 1].lr_) || (tr[rt << 1].lr_ && tr[rt << 1 | 1]._lr_ && c2[mid]));
        tr[rt]._lr = ((tr[rt << 1]._lr && tr[rt << 1 | 1].l_r) || (tr[rt << 1]._lr_ && tr[rt << 1 | 1]._lr && c2[mid]));
        tr[rt]._lr_ = ((tr[rt << 1]._lr && tr[rt << 1 | 1].lr_) || (tr[rt << 1]._lr_ && tr[rt << 1 | 1]._lr_ && c2[mid]));

    }
}
void build(int rt, int l, int r)
{
    if(l == r)
    {
        c1[l] = 0;
    }
    else 
    {
        int mid = (l + r) >> 1;
        c2[mid] = 0;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
    }
    maintain(rt, l, r);
}
void update(int rt, int v, int p, int l, int r)
{
    if(l == r)
    {
        c1[l] = v;
    }
    else 
    {
        int mid = (l + r) >> 1;
        if(p <= mid) update(rt << 1, v, p, l, mid);
        else update(rt << 1 | 1, v, p, mid + 1, r);
    }
    maintain(rt, l, r);
}
void update2(int rt, int v, int p, int l, int r)
{
    int mid = (l + r) >> 1;
    if(mid == p)
        c2[p] = v;
    else if(p < mid)
        update2(rt << 1, v, p, l, mid);
    else update2(rt << 1 | 1, v, p, mid + 1, r);
    maintain(rt, l, r);
}
pair<int, int> b[maxn];
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        int ans = INT_MAX;
        int n, m; scanf("%d%d", &n ,&m);
        build(1, 1, m);
        for(int i = 1, j = 0; i <= n; i++)
        {
            while(!tr[1].l_r && j < n)
            {
                j++;
                scanf("%d%d", &b[j].first, &b[j].second);
                if(b[j].first == b[j].second) update(1, 1, b[j].first, 1, m);
                else update2(1, 1, b[j].first, 1, m);
            }
            if(!tr[1].l_r) break;
            ans = min(ans, j - i + 1);
            if(b[i].first == b[i].second) update(1, 0, b[i].first, 1, m);
            else update2(1, 0, b[i].first, 1, m);
        }
        if(ans == INT_MAX) printf("-1\n");
        else printf("%d\n", ans);
    }
}

发表评论