[SCOI2015]国旗计划

非常考验技巧的一题...emm这个我最不会了...

首先断环为链,也就是把士兵和站台复制一份放在后面,这样只需要考虑覆盖一个区间而已

因为区间两两不包含,所以当选择了第个士兵后

现在覆盖了

那么从左端点不大于里选,一定是选右端点最大的最优秀了

那么这样选择的士兵就固定了...

关键就找下一个士兵的过程,可以二分预处理

但是倍增更快!!!

说起来 简单,但还是不会写,实现能力太差了...

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 4e5+10;
struct soldier
{
    int id,l,r;
}a[maxn];
bool com(soldier a,soldier b){ return a.l<b.l; }
int flow[maxn],f[maxn][22];
void solve(int k)
{
    int limit = a[k].l+m, ans = 1, index = k;
    for(int i=20;i>=0;i-- )
        if( f[k][i]!=0&&a[f[k][i]].r<limit )
            ans += (1<<i),k=f[k][i];
    flow[a[index].id] = ans+1;        
}
void init()
{
    for(int i=1,index = i;i<=2*n;i++)
    {
        while( index<=2*n && a[index].l<=a[i].r )    index++;//其实这里可以二分更快 
        f[i][0] = index-1;//最靠近r的战士,说明他的r也最远 
    }
    for(int i=1;i<=20;i++)
    for(int j=1;j<=2*n;j++)    
        f[j][i] = f[f[j][i-1]][i-1];
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        if( a[i].r<a[i].l )    a[i].r+=m;
        a[i].id = i;    
    }    
    sort( a+1,a+1+n,com );//注意先排序再复制 
    for(int i=n+1;i<=2*n;i++)
        a[i]=a[i-n],a[i].l+=m,a[i].r+=m;
    init();
    for(int i=1;i<=n;i++)    solve(i);
    for(int i=1;i<=n;i++)    printf("%d ",flow[i] );
}