题意：给你n个区间，从中选择m个，使得它们有交，且最长与最短区间的差值最小。
解：这道题我想了好多
的，nlog²n错的，nlogn错的，最后终于想出nlogn的了......
把区间按照长度排序，然后依次在线段树上加。
如果某一次等于m了，那么一个一个删，删到小于m的时候，更新答案。
证明：那些之前的区间如果想要成为答案，那么必须是和比当前这个还靠前的区间来组成。
这样的话当到这一个时，之前的要么被计算，要么不会更优。故可以删掉。
1 #include2 #include 3 4 const int N = 500010, INF = 0x3f3f3f3f; 5 6 int sum[N << 3], large[N << 3], tag[N << 3], X[N << 1]; 7 8 struct ITV { 9 int r, l, len;10 inline bool operator <(const ITV &w) const {11 return len < w.len;12 }13 }a[N];14 15 inline void pushup(int o) {16 int ls = o << 1;17 int rs = ls | 1;18 sum[o] = sum[ls] + sum[rs];19 large[o] = std::max(large[ls], large[rs]);20 return;21 }22 23 inline void pushdown(int l, int r, int o) {24 if(tag[o]) {25 int ls = o << 1;26 int rs = ls | 1;27 int mid = (l + r) >> 1;28 tag[ls] += tag[o];29 tag[rs] += tag[o];30 sum[ls] += (mid - l + 1) * tag[o];31 sum[rs] += (r - mid) * tag[o];32 large[ls] += tag[o];33 large[rs] += tag[o];34 tag[o] = 0;35 }36 return;37 }38 39 inline void add(int L, int R, int v, int l, int r, int o) {40 if(L <= l && r <= R) {41 tag[o] += v;42 sum[o] += v * (r - l + 1);43 large[o] += v;44 return;45 }46 pushdown(l, r, o);47 int mid = (l + r) >> 1;48 if(L <= mid) {49 add(L, R, v, l, mid, o << 1);50 }51 if(mid < R) {52 add(L, R, v, mid + 1, r, o << 1 | 1);53 }54 pushup(o);55 return;56 }57 58 int main() {59 60 int n, m;61 scanf("%d%d", &n, &m);62 for(int i = 1; i <= n; i++) {63 scanf("%d%d", &a[i].l, &a[i].r);64 a[i].len = a[i].r - a[i].l;65 X[i << 1] = a[i].l;66 X[(i << 1) - 1] = a[i].r;67 }68 std::sort(a + 1, a + n + 1);69 std::sort(X + 1, X + (n << 1) + 1);70 int t = std::unique(X + 1, X + (n << 1) + 1) - X - 1;71 int j = 1, ans = INF;72 for(int i = 1; i <= n; i++) {73 a[i].l = std::lower_bound(X + 1, X + t + 1, a[i].l) - X;74 a[i].r = std::lower_bound(X + 1, X + t + 1, a[i].r) - X;75 add(a[i].l, a[i].r, 1, 1, t, 1);76 while(large[1] >= m) {77 add(a[j].l, a[j].r, -1, 1, t, 1);78 //printf("large[1] = %d ans = %d \n i = %d j = %d \n", large[1], ans, i, j);79 ans = std::min(ans, a[i].len - a[j].len);80 j++;81 }82 }83 if(ans == INF) {84 ans = -1;85 }86 printf("%d\n", ans);87 return 0;88 }
这个sum其实是不必要的。
然后我还用动态开点写了一发......被卡空间了。
1 #include2 #include 3 4 const int N = 500010, INF = 0x3f3f3f3f; 5 6 int large[N * 31], tag[N * 31], root, ls[N * 31], rs[N * 31], tot; 7 8 struct ITV { 9 int r, l, len;10 inline bool operator <(const ITV &w) const {11 return len < w.len;12 }13 }a[N];14 15 inline void pushup(int o) {16 large[o] = std::max(large[ls[o]], large[rs[o]]);17 return;18 }19 20 inline void pushdown(int l, int r, int o) {21 if(tag[o]) {22 int mid = (l + r) >> 1;23 if(ls[o]) {24 large[ls[o]] += tag[o];25 tag[ls[o]] += tag[o];26 }27 if(rs[o]) {28 large[rs[o]] += tag[o];29 tag[rs[o]] += tag[o];30 }31 tag[o] = 0;32 }33 return;34 }35 36 inline void add(int L, int R, int v, int l, int r, int &o) {37 if(!o) {38 o = ++tot;39 }40 if(L <= l && r <= R) {41 tag[o] += v;42 large[o] += v;43 return;44 }45 if(!ls[o]) {46 ls[o] = ++tot;47 }48 if(!rs[o]) {49 rs[o] = ++tot;50 }51 pushdown(l, r, o);52 int mid = (l + r) >> 1;53 if(L <= mid) {54 add(L, R, v, l, mid, ls[o]);55 }56 if(mid < R) {57 add(L, R, v, mid + 1, r, rs[o]);58 }59 pushup(o);60 return;61 }62 63 int main() {64 65 int n, m, lm = 0;66 scanf("%d%d", &n, &m);67 for(int i = 1; i <= n; i++) {68 scanf("%d%d", &a[i].l, &a[i].r);69 a[i].len = a[i].r - a[i].l;70 lm = std::max(lm, a[i].r);71 }72 std::sort(a + 1, a + n + 1);73 int j = 1, ans = INF;74 for(int i = 1; i <= n; i++) {75 add(a[i].l, a[i].r, 1, 1, lm, root);76 while(large[1] >= m) {77 add(a[j].l, a[j].r, -1, 1, lm, root);78 //printf("large[1] = %d ans = %d \n i = %d j = %d \n", large[1], ans, i, j);79 ans = std::min(ans, a[i].len - a[j].len);80 j++;81 }82 }83 if(ans == INF) {84 ans = -1;85 }86 printf("%d\n", ans);87 return 0;88 }