题解：P7477 「C.E.L.U-02」划分可重集

zxh923 · 2025-07-19 17:00:48 · 题解

思路

很难评价这题调出来的时候我的精神状态。

首先这个 k 明显可以二分，所以直接二分就好。

然后我们可以发现，一个数要么扔到 a 里，要么扔到 b 里。既不能都扔进去也不能都不扔进去，所以这两个东西是互斥的，然后就可以用 2-SAT 做了。

我们的限制形如，如果一个数扔到某一个可重集里，那么值在一个区间内的数不能扔到这个集合里，然后受限制这些数的位置都在当前位置以前。

因为有这个位置的限制，所以我们不能使用线段树优化建图，而需要使用主席树优化建图。

首先先离散化一下。

然后这个东西和线段树优化建图其实没有本质区别，但是会遇到一个问题，就是如果有多个相同的数，我连边只会连最后一个，前面的就连不到了。

所以我们需要在离散化的时候把这个数的位置也加进去一块离散化，这样就没有上面提到的问题了。

剩下的就是 2-SAT 板子了。

代码

#include<bits/stdc++.h>
// #define int long long
#define N 20005
#define M N*20
#define K N*80
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define mpi make_pair
using namespace std;
int T=1,n,m,tot,v[N],id[N][2],pos[4][N];
int dfn[K],low[K],stk[K],ts,top,col,d[K];
int rt[4][N],lsh,inf=2e9;
pii a[N];
bool ist[K];
int h[K],e[K<<1],ne[K<<1],idx;
pii f[N];
void adde(int a,int b){
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
struct ds_out{
    struct node{
        int ls,rs,id;
    }tr[M];
    int cnt;
    void add(int &u,int las,int l,int r,int p,int v){
        u=++cnt;
        tr[u]=tr[las];
        tr[u].id=++tot;
        if(l==r){
            adde(v,tr[u].id);
            return;
        }
        int mid=l+r>>1;
        if(p<=mid)add(tr[u].ls,tr[las].ls,l,mid,p,v);
        else add(tr[u].rs,tr[las].rs,mid+1,r,p,v);
        if(tr[u].ls){
            adde(tr[tr[u].ls].id,tr[u].id);
        }
        if(tr[u].rs){
            adde(tr[tr[u].rs].id,tr[u].id);
        }
    }
    void modify(int u,int l,int r,int L,int R,int id){
        if(L>R)return;
        if(!u)return;
        if(l>=L&&r<=R){
            adde(tr[u].id,id);
            return;
        }
        int mid=l+r>>1;
        if(L<=mid)modify(tr[u].ls,l,mid,L,R,id);
        if(R>mid)modify(tr[u].rs,mid+1,r,L,R,id);
    }
}d1,d2;
struct ds_in{
    struct node{
        int ls,rs,id;
    }tr[M];
    int cnt;
    void add(int &u,int las,int l,int r,int p,int v){
        u=++cnt;
        tr[u]=tr[las];
        tr[u].id=++tot;
        if(l==r){
            adde(tr[u].id,v);
            return;
        }
        int mid=l+r>>1;
        if(p<=mid)add(tr[u].ls,tr[las].ls,l,mid,p,v);
        else add(tr[u].rs,tr[las].rs,mid+1,r,p,v);
        if(tr[u].ls){
            adde(tr[u].id,tr[tr[u].ls].id);
        }
        if(tr[u].rs){
            adde(tr[u].id,tr[tr[u].rs].id);
        }
    }
    void modify(int u,int l,int r,int L,int R,int id){
        if(L>R)return;
        if(!u)return;
        if(l>=L&&r<=R){
            adde(id,tr[u].id);
            return;
        }
        int mid=l+r>>1;
        if(L<=mid)modify(tr[u].ls,l,mid,L,R,id);
        if(R>mid)modify(tr[u].rs,mid+1,r,L,R,id);
    }
}d3,d4;
void tar(int u){
    dfn[u]=low[u]=++ts;
    stk[++top]=u;
    ist[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tar(j);
            low[u]=min(low[u],low[j]);
        }
        else if(ist[j])low[u]=min(low[u],dfn[j]);
    }
    if(low[u]>=dfn[u]){
        int y;
        col++;
        do{
            y=stk[top--];
            ist[y]=0;
            d[y]=col;
        }while(y!=u);
    }
}
void init(){
    for(int i=0;i<=tot;i++){
        dfn[i]=low[i]=0;
        ist[i]=0;
        d[i]=0;
        h[i]=-1;
    }
    d1.cnt=0;d2.cnt=0;
    d3.cnt=0;d4.cnt=0;
    for(int i=1;i<=n;i++){
        rt[0][i]=rt[1][i]=0;
        rt[2][i]=rt[3][i]=0;
    }
    col=top=ts=idx=0;
    tot=n*2;
}
bool check(int k){
    init();
    for(int i=1;i<=m;i++){
        int x=f[i].x,y=f[i].y;
        adde(id[x][0],id[y][1]);
        adde(id[y][0],id[x][1]);
        adde(id[x][1],id[y][0]);
        adde(id[y][1],id[x][0]);
    }
    int lim=lsh;
    for(int i=1;i<=n;i++){
        auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
        d1.add(rt[0][i],rt[0][i-1],1,lim,it,id[i][0]);
        d2.add(rt[1][i],rt[1][i-1],1,lim,it,id[i][1]);
        d3.add(rt[2][i],rt[2][i-1],1,lim,it,id[i][0]);
        d4.add(rt[3][i],rt[3][i-1],1,lim,it,id[i][1]);
    }
    for(int i=2;i<=n;i++){
        {
            tot++;
            auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
            auto it1=lower_bound(a+1,a+lsh+1,mpi(v[i]-k,inf))-a-1;
            d1.modify(rt[0][i],1,lim,it,it,tot);
            d4.modify(rt[3][i-1],1,lim,1,it1,tot);
            tot++;
            d1.modify(rt[0][i-1],1,lim,1,it1,tot);
            d4.modify(rt[3][i],1,lim,it,it,tot);
        }
        {
            tot++;
            auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
            auto it1=lower_bound(a+1,a+lsh+1,mpi(v[i]+k,0))-a;
            d2.modify(rt[1][i],1,lim,it,it,tot);
            d3.modify(rt[2][i-1],1,lim,it1,lim,tot);
            tot++;
            d2.modify(rt[1][i-1],1,lim,it1,lim,tot);
            d3.modify(rt[2][i],1,lim,it,it,tot);
        }
    }
    for(int i=1;i<=n*2;i++){
        if(!dfn[i]){
            tar(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(d[id[i][0]]==d[id[i][1]]){
            return 0;
        }
    }
    return 1;
}
void solve(int cs){
    if(!cs)return;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        a[i]={v[i],i};
    }
    sort(a+1,a+n+1);
    lsh=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=m;i++){
        cin>>f[i].x>>f[i].y;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<2;j++){
            id[i][j]=++tot;
        }
    }
    int l=0,r=1e9,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid-1;
            res=mid;
        }
        else l=mid+1;
    }
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cin>>T;
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    return 0;
}