题解--划分可重集

abruce · 2021-01-05 21:47:05 · 题解

一个奇异的想法，结果调了我一周多。。。

40pts(1)

二分很好看出来，关键在判定。
如果合法的话，一个数要么被划分进 a，要么被划分进 b，由此我们可以想用 2-SAT 去判定。这样，也能处理下面的 u 和 v 不在同一个可重集的问题。
对于那两个基本条件，我们可以对于每一个 j<i\ \text{and}\ v_j\le v_i-k 的 j 都连一条 j 选了 a,i 就不能选 a 的边。同理对于每一个 j<i\ \text{and}\ v_j\ge v_i+k 的 j 都连一条 j 选了 b,i 就不能选 b 的边。
我们现在可以暴力连边，虽然最多 n^2 条边，但前面 40 分的数据还是可以通过的。

40pts(2)

再看 m=0 的情况，a 中的每个数保证了 a_i<\min {a_j}+k，b 中的每个数保证了 b_i>\max {b_j}-k。
现在我们记录 a 中最小值和 b 中最大值，每次来一个数看能不能放进去，放哪一个更优一些，然后更新。
如果有一个放不进去，那就说明非法。（口胡算法）

100pts

显然这两个算法不能直接结合再一起，我们考虑优化其中一个算法。我们发现那个贪心算法比较难处理 u 和 v 之间不能连边，所以我们考虑优化第一个算法的连边过程。
这相当于实在 2-SAT 中向 j<i\ \text{and}\ v_j\le v_i-k 和 j<i\ \text{and}\ v_j\ge v_i+k 分别连边。这时我们可以使用主席树或者树状数组（orz ー念之间、、）优化建图。
假设将权值离散化后，我们将其建成了一个树状数组。

我们接下来假设往入树中插入了节点1和2。

通过当前树状数组节点指向上一个的旧节点，我们可以通过这样得到以前的信息，从而优化建图。我们进行连边时，每次连向当前的树状数组节点就可以得到相应的边。
注意细节。

#include<bits/stdc++.h>
using namespace std;
char __buf[1<<12],*__p1,*__p2;
//#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<12,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
inline int read() {
    int __x=0,__f=1;
    char __c=getchar();
    while(__c<'0'||__c>'9') {
        if(__c=='-')__f=-1;
        __c=getchar();
    }
    while(__c>='0'&&__c<='9') {
        __x=__x*10+__c-'0';
        __c=getchar();
    }
    return __x*__f;
}
char __F[200];
inline void write(int __x) {
    if(__x<0) {
        putchar('-');
        __x=-__x;
    }
    if(__x>=10)write(__x/10);
    putchar(__x%10+'0');
}
const int maxn=2e4+5,maxm=2e6+5;
struct edge {
    int next,to;
} e[maxm*4],w[maxn*8];
int a[maxn],g[maxn*2],book[maxn],bc,cnt,cnt2,h[maxm],dfn[maxm],low[maxm],col[maxm],color,n,m,s1[maxn][2],s2[maxn][2],tot,ans,ind,midd;
bool inst[maxm];
stack<int> s;
inline void addedge(int x,int y) {
    e[++cnt].next=h[x];
    e[cnt].to=y;
    h[x]=cnt;
}
inline void addedge2(int x,int y) {
    w[++cnt2].next=g[x];
    w[cnt2].to=y;
    g[x]=cnt2;
}
inline int lowbit(int x) {
    return x&(-x);
}
inline void add(int x,int y,int pd) {
//s1表示入树，s2表示出树。我们在向里面添加的时候，入树往它连边；它往出树连边。
    for(register int i=x; i<=bc; i+=lowbit(i)) {
        tot++;
        if(s1[i][pd]) {
            addedge(tot,s1[i][pd]);
            addedge(tot+1,s1[i][pd]+1);//往以前取到这个值的点连边
        }
        s1[i][pd]=tot;
        addedge(tot,y);
        addedge(tot+1,y+1);//把这个点挂在入树下面
        tot+=2;
        if(s2[i][pd]) {
            addedge(s2[i][pd],tot);//同理
            addedge(s2[i][pd]+1,tot+1);
        }
        s2[i][pd]=tot;
        addedge(y,tot);
        addedge(y+1,tot+1);
        tot++;
    }
}
inline void link(int x,int y,int pd) {
    int w=pd^1;
    for(register int i=x; i; i-=lowbit(i)) {
        if(s1[i][pd])addedge(y+pd,s1[i][pd]+w);//向对面连边
        if(s2[i][pd])addedge(s2[i][pd]+pd,y+w);
    }
}
inline void tarjan(int u) {
    s.push(u);
    inst[u]=1;
    dfn[u]=low[u]=++ind;
    for(register int i=h[u]; i; i=e[i].next) {
        int j=e[i].to;
        if(!dfn[j]) {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        } else if(inst[j]) {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(u<=n*2) {//注意这里可能造成的数组越界
        for(register int i=g[u]; i; i=w[i].next) {
            int j=w[i].to;
            if(!dfn[j]) {
                tarjan(j);
                low[u]=min(low[u],low[j]);
            } else if(inst[j]) {
                low[u]=min(low[u],dfn[j]);
            }
        }
    }
    if(dfn[u]==low[u]) {
        color++;
        int k;
        do {
            k=s.top();
            s.pop();
            inst[k]=0;
            col[k]=color;
        } while(k!=u);
    }
}
inline bool check(int mid) {
    memset(h,0,sizeof(h));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    cnt=ind=color=0;
    while(!s.empty()) {
        s.pop();
    }
    tot=2*n;
    for(register int i=1; i<=n; i++) {
        int p=upper_bound(book+1,book+bc+1,a[i]-mid)-book-1;//注意是upper_bound
        if(p)link(p,i*2-1,0);
        p=lower_bound(book+1,book+bc+2,a[i]+mid)-book;//这里右边界是bc+1
        if(p<=bc)link(bc-p+1,i*2-1,1);
        p=lower_bound(book+1,book+bc+1,a[i])-book;
        add(p,i*2-1,0);
        add(bc-p+1,i*2-1,1);
    }
    for(register int i=1; i<=2*n; i++) {
        if(!dfn[i]) {
            tarjan(i);
        }
    }
    for(register int i=1; i<=n; i++) {
        if(col[i*2-1]==col[i*2]) {
            return 0;
        }
    }
    return 1;
}
int main() {
    int x,y;
    n=read(),m=read();
    for(register int i=1; i<=n; i++) {
        a[i]=read();
        book[++bc]=a[i];
    }
    sort(book+1,book+bc+1);
    bc=unique(book+1,book+bc+1)-book-1;//离散化
    book[bc+1]=book[bc]+1;//注意往比它大的连边时所取的值能不能取到最后一个。
    for(register int i=1; i<=m; i++) {
        x=read(),y=read();
        addedge2(x*2-1,y*2);
        addedge2(x*2,y*2-1);
        addedge2(y*2,x*2-1);
        addedge2(y*2-1,x*2);
    }
    for(register int i=1; i<=2*n; i++) {
        if(!dfn[i]) {
            tarjan(i);
        }
    }
    for(register int i=1; i<=n; i++) {
        if(col[i*2-1]==col[i*2]) {
            puts("-1");
            return 0;
        }
    }
    int l=1,r=1e9;
    while(l<=r) {
        int mid=(l+r)/2;
        if(check(mid)) {
            ans=mid;
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    write(ans);
    return 0;
}