[SCOI2015]国旗计划

贪心 倍增

题面

有一个大小为$m$的环，其上有$n$个区间（互不包含）。对每个区间分别回答，如果必须使用该区间，最少需要多少区间才能完全覆盖环。

• $n\leq10^5,m\leq10^9$

解析

套路般地破环成链。区间能复制的也复制一边。

贪心显然，寻找一区间的后继者时，选左端点尽可能靠右、却又小于该区间右端点的区间。
（其实由于互不包含这一条件，排序以后，各区间左端点、右端点都具有单调性，所以说选右端点尽可能靠右的区间也可以）
于是可以预处理出每个区间的后继者。

注意到$m\leq10^9$，暴跳铁定$GG$，用倍增优化一下（或者说离散化，但实际上还是要倍增）。

记得在最右边设个极大值防止它跳得听不下来。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,top,len,mx,f[25][N],tot;
struct dat
{
  int l,r,id;
  bool operator < (const dat &o) const {return (l<o.l)||(l==o.l&&r<o.r);}
}a[N];
int ans[N];
bool vis[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int work(re int x)
{
  re int tar=a[x].l+m,now=x,res=0;
  fq(i,20,0)
    if(f[i][now]&&a[f[i][now]].r<tar) now=f[i][now],res+=(1ll<<i);
  return res+2;//开始区间和结束区间都没算
}
int main()
{
  tot=n=gi();m=gi();
  fp(i,1,n)
    {
      a[i].l=gi(),a[i].r=gi();a[i].id=i;
      if(a[i].l>a[i].r) a[i].r+=m;
      else a[++tot]=(dat){a[i].l+m,a[i].r+m,i};
    }
  sort(a+1,a+1+tot);a[tot+1].r=2e9;
  re int ysn=1;
  fp(i,1,tot)
    {
      while(ysn<=tot&&a[ysn+1].l<=a[i].r) ++ysn;
      f[0][i]=ysn;
    }
  fp(i,1,20) fp(j,1,tot) f[i][j]=f[i-1][f[i-1][j]];
  fp(i,1,tot) if(a[i].l<=m) ans[a[i].id]=work(i);
  fp(i,1,n) printf("%d ",ans[i]);puts("");
  return 0;
}