题解 P2898 【[USACO08JAN]haybale猜测Haybale Guessing】

· · 题解

广告：blog\spadesuit

P2898 【[USACO08JAN]haybale猜测Haybale Guessing】

题意：有一个没有重复数的正整数序列，每句话告诉你 l\sim r 区间的最小值为 f，求第一句与前面矛盾的话。

此题算法：并查集 + 二分

二分枚举第一句矛盾的话 x 。

拿出 1\sim x 句话，按 f 从大到小排序。

从左到右读每一句话：

如果出现两段没有重合区域的话满足 f 相等，得出矛盾。

如果出现所有 f 相等的话 \ll区域交\gg 已经全为一块，得出矛盾。

将所有相同 f 相等的话 \ll区域并\gg 合并为一块。

如果都不满足矛盾，就得出符合。

最后结束二分，得出第一句矛盾的话。

以下是代码 + 注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int Q=3e4+10;
int d(){int x;scanf("%d",&x);return x;}
int n,q;
struct ask{int l,r,f;}a[Q],cp[Q];
bool cmp(ask x,ask y){ //按 f 从大到小排序
    if(x.f==y.f) return x.l<y.l;
    return x.f>y.f;
}
struct mas{ //并查集
    int f[N];
    void clear(int x){
        for(int i=1;i<=x;i++)
            f[i]=i;
    }
    int find(int x){
        if(f[x]==x) return x;
        return f[x]=find(f[x]); 
    }
}s;
bool check(int x){ //判断1~x这些话矛不矛盾，原理如上
    s.clear(n+1);
    for(int i=1;i<=x;i++)
        cp[i]=a[i];
    sort(cp+1,cp+x+1,cmp);
    int p=cp[1].f,lx,ln,rx,rn;
    lx=ln=cp[1].l,rx=rn=cp[1].r;
    for(int i=2;i<=x;i++){
        if(p==cp[i].f){
            ln=min(ln,cp[i].l);
            rn=min(rn,cp[i].r);
            lx=max(lx,cp[i].l);
            rx=max(rx,cp[i].r);
            if(lx>rn) return 0;
        } else {
            if(s.find(lx)>rn) return 0;
            for(int j=s.find(ln);;j=s.find(j+1))
                if(j>rx) break;
                else s.f[j]=s.f[j+1];
            p=cp[i].f;
            lx=ln=cp[i].l;
            rx=rn=cp[i].r;
        }
    }
    return s.find(lx)<=rn;
}
int main(){
    n=d(),q=d();
    for(int i=1;i<=q;i++)
        a[i].l=d(),a[i].r=d(),a[i].f=d();
    int l=0,r=q+1;
    while(l<r-1){ //二分得出答案
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    if(r==q+1) puts("0");
    else printf("%d\n",r);
    return 0;
}

用线段树也可以做到，但又麻烦又慢。

画图、写题解不易，快点个赞吧。

谢谢大家! !