BZOJ4653: [Noi2016]區間(線段樹 雙指針)

題意

題目鏈接

Sol

按照dls的說法，一般這一類的題有兩種思路，一種是枚舉一個點$M$，然後check它能否成為答案。但是對於此題來說好像不好搞

另一種思路是枚舉最小的區間長度是多少，這樣我們把所有區間按長度排序後可以二分出滿足條件的最短的區間長度

觀察後不難發現，較長區間的長度一定是隨著短區間長度的增加而單調遞增的。

直接用雙指針維護即可。

判斷是否可行也就是是否有一個點被覆蓋了$m$次，離散化後線段樹維護。。

經驗：

1. 該類問題的兩種思路
2. 最大值的單調性

#include<bits/stdc++.h>
#define ls k << 1
#define rs k << 1 | 1
using namespace std;
const int MAXN = 4e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Node {
    int l, r, mx, f, siz; 
}T[MAXN];
struct Line {
    int l, r;
    bool operator < (const Line &rhs) const {
        return abs(r - l) <= abs(rhs.r - rhs.l);
    }
}a[MAXN];
int date[MAXN], num;
void add(int k, int val) {
    T[k].mx += val;
    T[k].f += val;
} 
void pushdown(int k) {
    if(!T[k].f) return ;
    add(ls, T[k].f); add(rs, T[k].f);
    T[k].f = 0;
}
void update(int k) {
    T[k].mx = max(T[ls].mx, T[rs].mx);
}
void Build(int k, int ll, int rr) {
    T[k].l = ll; T[k].r = rr;
    if(ll == rr) return ;
    int mid = ll + rr >> 1;
    Build(ls, ll ,mid); Build(rs, mid + 1, rr);
}
void Add(int k, int ll, int rr, int val) {
    if(ll <= T[k].l && T[k].r <= rr) {add(k, val); return ;}
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(ll <= mid) Add(ls, ll, rr, val);
    if(rr >  mid) Add(rs, ll, rr, val);
    update(k);
}
main() {
//  freopen("testdata.in", "r", stdin);
    N = read(); M = read();
    for(int i = 1; i <= N; i++) 
        a[i].l = read(), a[i].r = read(), date[++num] = a[i].l, date[++num] = a[i].r;
//  puts("-1");
    //sort(a + 1, a + N + 1);
    stable_sort(a + 1, a + N + 1);
//  puts("-1");
    sort(date + 1, date + num + 1);
    num = unique(date + 1, date + num + 1) - date - 1;
    for(int i = 1; i <= N; i++) a[i].l = lower_bound(date + 1, date + num + 1, a[i].l) - date,
                                a[i].r = lower_bound(date + 1, date + num + 1, a[i].r) - date;
    Build(1, 1, num);
    
    int ans = INF, now = 0;
    for(int i = 1; i <= N; i++) {
        while(T[1].mx < M && (now < N)) 
            now++, Add(1, a[now].l, a[now].r, 1); 
        if(T[1].mx >= M) ans = min(ans, date[a[now].r] - date[a[now].l] - ( date[a[i].r] - date[a[i].l]));
        Add(1, a[i].l, a[i].r, -1);
    }
    printf("%d\n", ans == INF ? -1 : ans);
}
/*
*/