题解 P4155【[SCOI2015]国旗计划】

cyffff · 2021-08-02 13:26:48 · 题解

\text{Link}

题意

一个 m 个点的环，有 n 条线段，可覆盖在环上 [c_i,d_i] 的部分，对 1\le i\le n 问强制选择线段 i 时，最少选择多少条线段可以覆盖整个环。

思路

这道题是校内模拟赛的 \text A 题，在考场上写出来了十分开心，就来写篇题解。

对于环，可以直接断环为链，变为线段覆盖问题。考虑线段不包含，则按照左端点排序后右端点单调，于是对于覆盖整个环，选择线段 i 的下一段的线段 j 是固定的，j=\max\{x|c_x\le d_i\}。

考虑计算出每个 i 的下一条线段，然后倍增求出每条线段的下 2^k 条线段。

对于一次询问，倍增至 d_j<c_i+m 即可，注意要将答案 +2，即这一条线段与最后的线段。

这道题就做完了！时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff

}
const int N=2e5+10;
int n,m,answ[N];
int st[20][N<<1];
struct segment{
    int l,r,id;
    inline friend bool operator<(const segment &a,const segment &b){
        return a.l<b.l;
    }
}a[N<<1];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        int l=read(),r=read();
        if(l>r) r+=m;
        a[i].l=l,a[i].r=r,a[i].id=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        a[i+n].l=a[i].l+m,a[i+n].r=a[i].r+m;
    for(int i=1,j=1;i<=2*n;i++){
        while(j<=2*n&&a[j].l<=a[i].r)
            j++;
        st[0][i]=j-1;
    }
    for(int i=1;i<=19;i++)
        for(int j=1;j<=2*n;j++)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=1;i<=n;i++){
        int up=a[i].l+m,ans=0,p=i;
        for(int j=19;j>=0;j--)
            if(st[j][p]&&a[st[j][p]].r<up)
                ans+=1<<j,p=st[j][p];
        answ[a[i].id]=ans+2;
    }
    for(int i=1;i<=n;i++)
        write(answ[i]),putc(' ');
    flush();
}

再见 qwq~