题解 [NOI2016] 区间

题意

题目链接：传送门

题面比较简洁了。

碎碎念

开学前一天颓着颓着就看到这道题了

一开始想了一个假的做法：用一颗线段树维护 \([L,R]\) 的最小花费和最大权值，大概写了
\(30min\)之后发现没办法维护最大最小区间长........

然后 看了一眼题解看到了尺取法这三个字，又看了看标签里有排序，然后就没有然后了———

Solution

首先注意到一个性质：增加一个区间不会使答案更优，去掉一个区间不会使答案变差

进而注意到对于一个区间的集合 \(S\),令\(min(S)=a,max(S)=b\)，则长度在\([a,b]\)中的区间对答案没有影响，也就是说它们是可有可无的。

于是我们得出一个结论，最优解的所有区间长度必然可以连续

按区间长度升序将所有区间排序，然后双指针扫扫一遍，右指针向前扫，不断更新区间最大值，当这个最大值（也就是区间内一个点被覆盖最多次数）大于等于\(m\)时，左指针向前走直到区间最大又小于\(m\)

显然区间最值可以用线段树维护，总的复杂度\(O(nlogn)\)

#include
#define rep(a,b,c) for (register int a=b;a<=c;a++)
#define per(a,b,c) for (register int a=b;a>=c;a--)
using namespace std;
typedef long long ll;
template  inline void read(T &x){
	ll f = 1;x = 0;char ch = getchar();
	while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}
	while (isdigit(ch)){x = (x << 1)+(x << 3)+(ch ^ 48);ch = getchar();}
	x *= f;
}

const int MAXN=500100; 

int n,m;

int b[MAXN*2],cnt,tot;

struct Section{
	int x,y,len;
	bool operator < (const Section &X) const
	{
		return len==X.len?x>1;
		build(pos<<1,L,mid);
		build(pos<<1|1,mid+1,R); 
	}
	
	inline void push_up(int pos)
	{
		maxv(pos)=max(maxv(pos<<1),maxv(pos<<1|1));
	}
	
	inline void push_down(int pos)
	{
		maxv(pos<<1)+=tag(pos),maxv(pos<<1|1)+=tag(pos);
		tag(pos<<1)+=tag(pos),tag(pos<<1|1)+=tag(pos);
		tag(pos)=0;
	}
	
	inline void modify(int pos,int L,int R,int val)
	{
		if(l(pos)>=L&&r(pos)<=R) 
		{
			maxv(pos)+=val;
			tag(pos)+=val;
			return;
		}
		if(l(pos)==r(pos))return;
		if(tag(pos))push_down(pos);
		int mid=l(pos)+r(pos)>>1;
		if(L<=mid)modify(pos<<1,L,R,val);		
		if(R>mid)modify(pos<<1|1,L,R,val);
		push_up(pos);
	} 
		
}T;

inline void init()
{
	scanf("%d%d",&n,&m);
	
	rep(i,1,n)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		b[++tot]=a[i].x,b[++tot]=a[i].y;
		a[i].len=a[i].y-a[i].x;
	}
	sort(a+1,a+n+1);
	sort(b+1,b+tot+1);
	cnt=unique(b+1,b+tot+1)-b-1;
	 
}

inline void solve()
{
	T.build(1,1,cnt);
	int lpos,rpos;
	lpos=rpos=1;
	
	int ans=1e9; 
	while(lpos<=rpos&&rpos<=n)
	{
	
		int L=lower_bound(b+1,b+cnt+1,a[rpos].x)-b;
		int R=lower_bound(b+1,b+cnt+1,a[rpos].y)-b;	
		T.modify(1,L,R,1);
		
		while(T.maxv(1)>=m&&lpos