【题解】P1712 [NOI2016]区间(贪心+线段树)

一个observe是，对于一个合法的方案，将其线段长度按照从大到小排序后，他极差的来源是第一个和最后一个。或者说，读入的线段按照长度分类后，答案是一段子序列。所以我们考虑枚举右端点，尺取法取右边的线段，去到可以满足条件时将左边的这条线段删除。现在就是要维护一个数据结构可以得到是否存在一个点被覆盖了\(m\)次，直接线段树维护每个点被覆盖多少次即可。就是线段树支持区间加和求区间单点最值。

1A掉了很舒爽代码

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=5e5+5;

const int inf=1e9+7;

int n,m,sav[maxn<<1];

typedef pair<int,pair<int,int>> P;

P data[maxn];

struct Seg{

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

#define lef L,R,l,mid,pos<<1

#define rgt L,R,mid+1,r,pos<<1|1

      struct E{int val,tag;}seg[maxn<<3];

      inline void pd(const int&pos){

	    if(seg[pos].tag==0)return;

	    seg[pos<<1].val+=seg[pos].tag;

	    seg[pos<<1|1].val+=seg[pos].tag;

	    seg[pos<<1].tag+=seg[pos].tag;

	    seg[pos<<1|1].tag+=seg[pos].tag;

	    seg[pos].tag=0;

      }

      void upd(const int&k,const int&L,const int&R,const int&l,const int&r,const int&pos){

	    if(L>r||R<l) return;

	    if(L<=l&&r<=R) {seg[pos]={seg[pos].val+k,seg[pos].tag+k}; return;}

	    pd(pos);

	    upd(k,lef); upd(k,rgt);

	    seg[pos].val=max(seg[pos<<1].val,seg[pos<<1|1].val);

      }

      int que(const int&L,const int&R,const int&l,const int&r,const int&pos){

	    if(L>r||R<l) return 0;

	    if(L<=l&&r<=R) return seg[pos].val;

	    pd(pos);

	    int ret=max(que(lef),que(rgt));

	    seg[pos].val=max(seg[pos<<1].val,seg[pos<<1|1].val);

	    return ret;

      }

}s;

int main(){

      n=qr(); m=qr();

      for(int t=1,t1,t2;t<=n;++t)

	    t1=qr(),t2=qr(),data[t]={t2-t1,{t1,t2}},sav[++*sav]=t1,sav[++*sav]=t2;

      sort(data+1,data+n+1,[&](const P&a,const P&b){return a>b;});

      sort(sav+1,sav+*sav+1);

      int len=unique(sav+1,sav+*sav+1)-sav-1;

      for(int t=1;t<=n;++t)

	    data[t].second.first=lower_bound(sav+1,sav+len+1,data[t].second.first)-sav,

		  data[t].second.second=lower_bound(sav+1,sav+len+1,data[t].second.second)-sav;

      int ans=inf;

      for(int t=1,r=0;t<=n;++t){

	    while(r<n&&s.que(1,len,1,len,1)<m)

		  ++r,s.upd(1,data[r].second.first,data[r].second.second,1,len,1);

	    if(s.que(1,len,1,len,1)>=m) ans=min(ans,data[t].first-data[r].first);

	    s.upd(-1,data[t].second.first,data[t].second.second,1,len,1);

      }

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

      return 0;

}