先按照長度排個(gè)序，然后依次添加區(qū)間。什么是添加？設(shè)這個(gè)區(qū)間是\([l,r]\)，添加就是把\(a_l,a_{l+1},a_{l+2},{...},a_{r}\)都加上\(1\)，其中\(a_i\)表示第\(i\)個(gè)位置被幾個(gè)區(qū)間覆蓋。拿走一個(gè)區(qū)間的含義就是把它們都減\(1\)。這個(gè)過程很顯然可以用線段樹維護(hù)。

如果在添加到一個(gè)區(qū)間 \(i\) 時(shí)，有一個(gè)點(diǎn)被區(qū)間覆蓋了\(M\)次，那么先更新答案，再把前面的加入過的區(qū)間一直拿直到?jīng)]有一個(gè)點(diǎn)被覆蓋\(M\)次。如何判斷有沒有點(diǎn)被覆蓋\(M\)次？因?yàn)槭且粋€(gè)一個(gè)區(qū)間加的，所以只用維護(hù)一個(gè)\(a_i\)的最大值，看他是否\(=M\)就行了。

什么叫再把前面的加入過的區(qū)間一直拿直到?jīng)]有一個(gè)點(diǎn)被覆蓋\(M\)次？

比如你一直添加區(qū)間到第\(5\)個(gè)，此時(shí)有一個(gè)點(diǎn)被覆蓋了\(M\)次。這時(shí)你就將第一個(gè)區(qū)間拿出，如果此時(shí)依然有有一個(gè)點(diǎn)被覆蓋了\(M\)次，那么你就拿走第二個(gè)...

這個(gè)過程就好比一個(gè)隊(duì)列，可以從后面添加區(qū)間達(dá)到一個(gè)點(diǎn)被覆蓋了\(M\)次；從前面彈出區(qū)間直到?jīng)]有一個(gè)點(diǎn)被覆蓋了\(M\)次。

差不多就是這樣，還有注意一下\(l_i,r_i \leq 10^9\)，開線段樹是要離散化的。上代碼：

#include <bits/stdc++.h> #define INF 1000000001 using namespace std; const int N = 500500; int n, m, cnt, tot, ans = INF; struct Seg {int l, r, len;bool operator < (const Seg &x) const {return len < x.len;} }a[N]; struct KEY {int d, id, se; }key[N * 2]; inline bool cmp1(KEY x, KEY y) {return x.d < y.d; } inline bool cmp2(KEY x, KEY y) {return x.id < y.id; } struct node {int left, right, Max, lazy;node *ch[2]; }pool[N * 4], *root; inline void pushup(node *r) {r->Max= max(r->ch[0]->Max, r->ch[1]->Max); } inline void pushdown(node *r) {if(!r->lazy) return ;r->Max += r->lazy;if(r->ch[0]) r->ch[0]->lazy += r->lazy;if(r->ch[1]) r->ch[1]->lazy += r->lazy;r->lazy = 0; return ; } inline void build(node *r, int left, int right) {r->left = left, r->right = right;if(left == right) return ;int mid = (left + right) >> 1;node *lson = &pool[++cnt], *rson = &pool[++cnt];r->ch[0] = lson, r->ch[1] = rson;build(lson, left, mid), build(rson, mid + 1, right); } inline void change(node *r, int left, int right, int d) {if(r->left == left && r->right == right) {r->lazy += d; return ;}pushdown(r);if(r->ch[0]->right >= right) change(r->ch[0], left, right, d);else if(r->ch[1]->left <= left) change(r->ch[1], left, right, d);else change(r->ch[0], left, r->ch[0]->right, d), change(r->ch[1], r->ch[1]->left, right, d);pushdown(r->ch[0]), pushdown(r->ch[1]), pushup(r); } int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d%d", &a[i].l, &a[i].r);a[i].len = a[i].r - a[i].l;key[++tot].d = a[i].l, key[tot].id = tot;key[++tot].d = a[i].r, key[tot].id = tot;}sort(key + 1, key + tot + 1, cmp1);key[0].d = -1; key[0].se = 0;for(int i = 1; i <= tot; i++)if(key[i].d == key[i - 1].d) key[i].se = key[i - 1].se;else key[i].se = key[i - 1].se + 1;sort(key + 1, key + tot + 1, cmp2);for(int i = 1; i <= n; i++)a[i].l = key[i * 2 - 1].se, a[i].r = key[i * 2].se;sort(a + 1, a + n + 1);build(root = &pool[0], 1, 2 * n + 1);int pos = 1;change(root, a[1].l, a[1].r, 1);if(m == 1) ans = 0;for(int i = 2; i <= n; i++) {change(root, a[i].l, a[i].r, 1);while(root->Max >= m) {change(root, a[pos].l, a[pos].r, -1);ans = min(ans, a[i].len - a[pos].len);pos++;} }if(ans == INF) ans = -1;printf("%d\n", ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/acfunction/p/10051289.html

總結(jié)

以上是生活随笔為你收集整理的题解【bzoj4653 [NOI2016] 区间】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。