P4155 [SCOI2015] 国旗计划——倍增加速贪心

li_cat · 2025-05-17 22:15:58 · 个人记录

先看数据范围， n \ge 10^5

破环为链这个比较自然，但是对于如何求解并没有思路

苦思冥想没有思路，直接打暴力

枚举以每一个士兵为开始，对右侧进行最小次数区间覆盖

考虑贪心，如果加入一个区间，那么这个区间在不会制造出空隙的情况下应该尽可能右端点靠右

每一次时间复杂度 O(n) ，总共 O(n^2)

让我们来重新审视贪心的这个过程，事实上是不断寻找并加入新的最优区间的过程

可以发现，对于已经选择了的最右端的区间来说，它接下来选择的最优区间是确定的

那么，我们就可以对这个进行预处理

预处理之后，我们发现每次的贪心中除了可以一次次地跳跃，还可以一次跳很多

考虑倍增维护，像LCA一样寻找填充完目标区间完前的那个区间，途中记录跳过的区间总数

时间复杂度 O(n \log n)

(区间端点记得弄清楚)

AC Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e5+5;

int nxt[MAXN<<1][25],ans[MAXN];
int n,m,top=0;

struct RANGE{
    int l,r,idx;
}range[MAXN<<1];

bool cmp(RANGE x,RANGE y){
    return x.l<y.l;
}//

void getnxt(){
    int j=1,r;
    for(int i=1;i<=top;++i){
        r=range[i].r;
        while(j+1<=top && range[j+1].l<=r)
            ++j;
        nxt[i][0]=j;
    }
}//

void getst(){
    for(int i=1;(1<<i)<=top;++i)
        for(int j=1;j<=top;++j)
            nxt[j][i]=nxt[nxt[j][i-1]][i-1];
}//

int query(int idx){
    int R=range[idx].l+m,res=2;

    for(int i=21;i>=0;--i){
        if(!nxt[idx][i]) continue;
        if(range[nxt[idx][i]].r<R){
            idx=nxt[idx][i];
            res+=(1<<i);
        }
    }
    return res;
}//

void work(){
    scanf("%d%d",&n,&m);
    for(int i=1,l,r;i<=n;++i){
        scanf("%d%d",&l,&r);
        if(l>r) r+=m;
        range[++top].idx=i;
        range[top].l=l;range[top].r=r;
//      if(r<=m){
            range[++top].l=l+m;
            range[top].r=r+m;
//      }
    }

    sort(range+1,range+1+top,cmp);

    getnxt();
    getst();

    for(int i=1;i<=top;++i){
        if(range[i].idx){
            ans[range[i].idx]=query(i);
        }
    }

    for(int i=1;i<=n;++i){
        printf("%d ",ans[i]);
    }
}

int main(){
    work();
    return 0;
}