P6902

Aryper · 2021-10-07 23:10:59 · 个人记录

[ICPC2014 WF]Surveillance

我们首先想到断环为链再复制，所以只要想办法解决链上的问题就好了。

然后我们知道可以先选定某个线段，然后再可以接上它的线段中选择右端点最大的，然后再更新右端点再选择。这样选定每个线段的时间复杂度 O(k)，扩展右端点时间复杂度 O(k)，总的复杂度是 O(k^2) 的。

现在使用倍增优化。

定义 f(i,j) 表示选定了第 i 条线段，进行 2^j 次扩展后能扩展到哪一条线段（右端点最大）。

这样以后，在选定线段之后，我们就可以倍增扩展至需要的位置，时间复杂度是 O(k\log k) 的。

最后解决的问题就是计算 f(i,0)。因为事先按照左端点排序，用来方便倍增扩展，所以这个时候我们可以用一个可重集来寻找下一条要选择的线段，时间复杂度 O(k\log k)。

最后注意的是，因为这个方法事先已经选好了一条线段，所以对于只用 1 条线段就能覆盖的情况需要特判一下。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,k,ans,tot,it;

ll f[N*2+5][25];

struct node{
    ll l,r;
    bool operator < (const node &rhs) const {
        return l==rhs.l?(r<rhs.r):(l<rhs.l);
    }
}a[N*2+5];

multiset<pair<ll,ll>> s;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();k=read();

    for(ll i=1;i<=k;i++) {
        ll x,y;
        x=read();y=read();
        if(x<=y) {
            a[++tot].l=x;a[tot].r=y;
            a[++tot].l=x+n;a[tot].r=y+n;
        }
        else {
            a[++tot].l=x;a[tot].r=y+n;
        }
    }

    sort(a+1,a+tot+1);

    it=0;
    for(ll i=1;i<=tot;i++) {
        f[i][0]=i;
        s.insert({a[i].r,i});
        while(s.begin()->first<a[i].l-1) {
            f[s.begin()->second][0]=it;s.erase(s.begin());
        }
        if(a[i].r>a[it].r) it=i;
    }

    while(!s.empty()) {
        f[s.begin()->second][0]=it;s.erase(s.begin());
    }

    for(ll j=1;j<=22;j++) {
        for(ll i=1;i<=tot;i++) {
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }

    ans=1e9;
    for(ll i=1;i<=tot;i++) {
        ll x=i,tmp=0;
        if(a[i].r-a[i].l+1>=n) ans=min(ans,1ll);
        for(ll j=22;j>=0;j--) {
            if(a[f[x][j]].r<n+a[i].l-1) {
                x=f[x][j];tmp+=1<<j;
            }
        }
        x=f[x][0];
        if(a[x].r>=n+a[i].l-1) ans=min(ans,tmp+2);
    }

    if(ans>k) printf("impossible");
    else write(ans);

    return 0;
}