【题解】LOJ 2086 「NOI2016」区间

Problem

给定 $n$ 个区间,现需要选出 $m$ 个区间,使得这 $m$ 个区间共同包含至少一个位置,并令这 $m$ 个区间中最大长度 - 最小长度尽可能小

求最小长度差是多少

Thought

将区间按照长度进行排序,很容易发现根据最长区间向右移动,最短区间也向右移动

可以使用two-pointer,线段树 $check$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 500010;

int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '0') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

struct Interval {
    int l, r, len;
    bool operator < (const Interval x) {
        return len < x.len;
    }
}p[N];
int X[N << 1], cntX;
int L[N << 1], cntL;

struct Tree {
    int ch[N << 2][2], cnt = 1;
    int num[N << 2], tag[N << 2];
    #define L (ch[x][0])
    #define R (ch[x][1])
    #define mid ((l + r) >> 1)
    void pushdown(int x) {
        tag[L] += tag[x];
        tag[R] += tag[x];
        num[L] += tag[x];
        num[R] += tag[x];
        tag[x] = 0;
    }
    void add(int x, int l, int r, int ll, int rr, int key) {
        if(l >= ll && r <= rr) {
            tag[x] += key;
            num[x] += key;
        }
        else {
            if(!L) L = ++ cnt;
            if(!R) R = ++ cnt;
            if(tag[x]) pushdown(x);
            if(mid >= ll)
                add(L, l, mid, ll, rr, key);
            if(mid < rr)
                add(R, mid + 1, r, ll, rr, key);
            num[x] = max(num[L], num[R]);
        }
    }
    #undef L
    #undef R
    #undef mid
}tr;
int n, m;
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        p[i].l = read(); p[i].r = read();
        p[i].len = p[i].r - p[i].l;
        X[++ cntX] = p[i].l;
        X[++ cntX] = p[i].r;
        L[++ cntL] = p[i].len;
    }
    sort(X + 1, X + cntX + 1);
    sort(L + 1, L + cntL + 1);
    cntX = unique(X + 1, X + cntX + 1) - X - 1;
    cntL = unique(L + 1, L + cntL + 1) - L - 1;
    for(int i = 1; i <= n; ++ i) {
        p[i].l = lower_bound(X + 1, X + cntX + 1, p[i].l) - X;
        p[i].r = lower_bound(X + 1, X + cntX + 1, p[i].r) - X;
    }
    sort(p + 1, p + n + 1);
    int head = 1, tail = 0, ans = INT_MAX;
    while(tail < n) {
        ++ tail;
        tr.add(1, 1, cntX, p[tail].l, p[tail].r, 1);
        while(tail < n && p[tail + 1].len ==  p[tail].len) {
            ++ tail;
            tr.add(1, 1, cntX, p[tail].l, p[tail].r, 1);
        }
        while(tr.num[1] >= m) {
            ans = min(ans, p[tail].len - p[head].len);
            int now = head;
            tr.add(1, 1, cntX, p[head].l, p[head].r, - 1);
            ++ head;
            while(p[head].len == p[head - 1].len) {
                tr.add(1, 1, cntX, p[head].l, p[head].r, - 1);
                ++ head;
            }
        }
    }
    printf("%d\n", ans == INT_MAX ? - 1 : ans);
    return 0;
}
Comments

添加新评论