题目描述

有M个边防站，N个可以从Ci走到Di的边防战士，问你在已经选择某个边防战士时，至少需要多少个边防战士才能绕着边防走一圈。

可以抽象成一个有M个坐标点的圆，和N个区间，问你在已经选择某个区间的情况下，至少要选择多少区间才能将这个圆圈包含在内。

因为所有的区间都不互相包含，所以对于区间a和b，如果Ca<Cb，那么Da<Db。也就是说区间是可以排序的。那么对于区间i，向后遍历一下就能得到与i有交集（Di<Cj）的，右端点最远的区间j。

对于这个有M个坐标的圆，因为数据保证整个边境线都是可覆盖的，所以我们可以用这N个区间的集合来表示它，但如果只在数组里存储这N个区间，我们在对某个区间向后遍历的时候会很麻烦，因为有左端点大于右端点的情况。

所以我们用化圆为线的的思想来解决，读入N个区间时若左端点大于右端点，则将右端点加M。再读入前N个区间后排一次序，然后将这N个区间复制到自己的后边，复制品左右端点都加M。这样就相当于吧一个有M个坐标点的圆变成了有2M个坐标点的线段，且保持了N个区间首尾相接的特性。

完成数据的抽象接下来就是从每个区间往后走，看至少需要几个区间能走满一个M。

很容易想到用贪心的方法来做，对于区间i，遍历他之后的N个区间，每找到相交的最远区间，ans++。这样的时间复杂度是n^2，超时。

用倍增的方法来优化。对于每个区间s，我们如果连续找2^i次相交最远区间，这个时候到达的区间为go[s][i]。这个数组用一个简单的动态规划求出来，递推关系式是
go[s][i]=go[go[s][j-1]][j-1]。
也就是从s出发先走2^(j-1)次，再走2^(j-1)次。而边界是go[s][0]。就是从s出发走2^0也就是1次，通过一个贪心就求出来了。

初始化好go数组后，对于区间x，先定义cur等于x，然后做一个for循环让i从log2N到0，如果go[cur][i]<区间x的右端点+M，则说明这一步不会走过头，可以走，就把cur更新为go[cur][i]，ans+2^i。把所有i计算过后，这时的cur就是刚好再走一步走完一圈的区间。相当于将一个十进制A数转化为二进制，就从一个很高的二进制位来往下计算，假设是第k位，如果2^k比A小，这一位取1，然后A减去2^k，否则取0。计算完所有位后A一定就被减光了，也就得到了二进制的A。

这样做对于每个区间，只用logN的复杂度，总复杂度nlogn，ac。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(倍增) $O(nlogn)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m;
struct warrior{
    int id,l,r;
    bool operator<(const warrior t)const{
        return l<t.l;
    }
}w[N*2];
int n2;
int go[N][20];
void init(){
    int nxt=1;
    for(int i=1;i<=n2;i++){
        while(nxt<=n2&&w[nxt].l<=w[i].r)
            nxt++;
        go[i][0]=nxt-1;
    }
    for(int i=1;1<<i<=n;i++)
        for(int s=1;s<=n2;s++)
            go[s][i]=go[go[s][i-1]][i-1];
}
int res[N];
void search(int x){
    int end=w[x].l+m,cur=x,ans=1;
    for(int i=log2(n);i>=0;i--){
        int pos=go[cur][i];
        if(pos&&w[pos].r<end){
            cur=pos;
            ans+=1<<i;
        }
    }
    res[w[x].id]=ans+1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        w[i].id=i;
        cin>>w[i].l>>w[i].r;
        if(w[i].r<w[i].l)w[i].r+=m;
    }
    sort(w+1,w+1+n);
    n2=2*n;
    for(int i=n+1;i<=n2;i++){
        w[i]=w[i-n];
        w[i].l+=m;
        w[i].r+=m;
    }
    init();
    for(int i=1;i<=n;i++)search(i);
    for(int i=1;i<=n;i++)cout<<res[i]<<' ';
    return 0;
}