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);
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

两个字符串算法

这部分主要使用了动态规划的技术,就是如果两个最大公共子序列相等的话,必然前面的也相等

512
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

56210
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1082
来自专栏五分钟学算法

每天一算:Odd Even Linked List

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

1103
来自专栏前端杂谈

前端算法-基本排序算法比较

36913
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1433
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1977
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

2908
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3515
来自专栏Bingo的深度学习杂货店

Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element ...

2776

扫码关注云+社区

领取腾讯云代金券