luogu P1712 [NOI2016]区间

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1

输入描述:

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

输出描述:

只有一行，包含一个正整数，即最小花费。

按照区间长度排序，把区间端点离散化.

这样做不影响答案，我们也可以更加方便处理

线段树区间维护最大值就解决了

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10,inf=1<<30;

#define int long long

#define ls (p<<1)

#define rs (p<<1)|1

struct node{

	int l,r,sum,add;

	#define l(x) tree[x].l

	#define r(x) tree[x].r

	#define sum(x) tree[x].sum

	#define add(x) tree[x].add

}tree[4*N];

#define mid ((l(p)+r(p))>>1)

inline void pushdown(int p){

	add(ls)+=add(p);

	add(rs)+=add(p);

	sum(ls)+=add(p);

	sum(rs)+=add(p);

	add(p)=0;

}

inline void build(int p,int l,int r){

	l(p)=l,r(p)=r;

	if(l==r)return;

	build(ls,l,mid);

	build(rs,mid+1,r);

}

inline int ask(int p,int l,int r){

	if(l<=l(p)&&r(p)<=r)return sum(p);

	int ans=0;

	if(add(p))pushdown(p);

	if(l<=mid)ans=max(ans,ask(ls,l,r));

	if(r>mid)ans=max(ans,ask(rs,l,r));

	return ans;

}

inline void change(int p,int l,int r,int d){

	if(l<=l(p)&&r(p)<=r){sum(p)+=d;add(p)+=d;return;}

	if(add(p))pushdown(p);

	if(l<=mid)change(ls,l,r,d);

	if(r>mid)change(rs,l,r,d);

	sum(p)=max(sum(ls),sum(rs));

}

struct E{

	int l,r,len;

}e[N];

bool cmp(E t1,E t2){return t1.len<t2.len;}

int A[N],n,m;

signed main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		scanf("%lld%lld",&e[i].l,&e[i].r);

		e[i].len=e[i].r-e[i].l;

		A[i]=e[i].l;

		A[i+n]=e[i].r;

	}

	sort(A+1,A+1+2*n);sort(e+1,e+1+n,cmp);

	int len=unique(A+1,A+1+2*n)-A-1;

	for(int i=1;i<=n;i++){

		e[i].l=lower_bound(A+1,A+1+len,e[i].l)-A;

		e[i].r=lower_bound(A+1,A+1+len,e[i].r)-A;

	}

	build(1,1,2*n);

	int l=1,r=0,ans=inf;

    while(r<n){

        while(r<n&&sum(1)<m){++r;change(1,e[r].l,e[r].r,1);}

        if(sum(1)<m)break;int tmp;

        while(sum(1)>=m)tmp=e[l].len,change(1,e[l].l,e[l].r,-1),++l;

        ans=min(ans,e[r].len-tmp);

    }

    printf("%lld\n",ans==inf?-1:ans);

}

巴特西

luogu P1712 [NOI2016]区间

题目描述

输入描述:

输出描述:

最新文章

热门文章