P1410题解

· · 题解

竟然没有低于 O(n^2) 的解法（那个 O(n\log n) 的是假的），那就让我讲一个吧。

首先考虑哪些数不能被分到同一集合里，显然是 i<j,a_i ≥a_j 的（以下称“逆序对”）。

对于所有逆序对，我们在它们中间建一条边。如果最后的图是二分图，那显然可以被划分成两个集合。

没有奇环的图是二分图，反之则是，让我们看看奇环在数组中长啥样：

所以把最长不升子序列长度大于 2 的判掉即可。Dilworth 定理也可以推出这一点。

把二分图的点分成两个集合，无非就是将其染色。一个联通二分图的染色方案数唯二，也就是黑白反置而已。

要求染色的两点的数量怎么办？二分图边数可能是 O(n^2) 的。其实我们只需保证联通性，对于每个点建一条最靠后的边，如果没有出边就等待被其他数更新（指针维护），这样一定不劣，细节请看代码。

有很多联通块呢？问题就是很多的二选一，选出来的点数总和恰好等于 n/2。这是经典背包问题。

直接朴素背包是 O(n^2) 的，还需优化。设要选两数为 p 和 q，把 \min(p,q) 拿出来加到答案里，就转化成“选不选 \max(p,q)-\min(p,q) 加到答案里”的问题。

注意到 \max(p,q)-\min(p,q) 的种类数不超过 O(\sqrt n)，因为其总和不超过 n。所以大多这样的贡献都是重复的，可以把它看作多重背包做二进制分解，这样最多转移 O(\sqrt n \log n) 次，还卡不到这个量级。

还没完，dp 状态只有 0 和 1，所以可以用 bitset 优化。

时间复杂度 O(\frac {n\sqrt n \log n} {w})，跑的飞快，是目前最优解。

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
#define pii pair<int,int>
using namespace std;
const int N=2e5+7;
int n,m,x,a[N],t[N],u,v,idx,dp[N],nxt[N];
int f[N],cnt,mx,la,w[N],ans;
pii p[N];
bool vis[N],op[N];
bitset<N/2> d;
inline void modi(int k,int x){
    while(k<=cnt) t[k]=max(t[k],x),k+=lowbit(k);
}
inline int ask(int k){
    int res=0;
    while(k) res=max(res,t[k]),k-=lowbit(k);
    return res;
}
inline bool check(){
    for(int i=1;i<=cnt;i++) t[i]=0;
    for(int i=1;i<=n;i++){
        dp[i]=ask(cnt+1-a[i])+1,modi(cnt+1-a[i],dp[i]);
        if(dp[i]>=3) return 0;
    }
    return 1;
}
inline int func(int l,int r){
    for(int i=l;i<=r;i++) vis[i]=op[i]=0;
    int idx=r,cnt=1,cnt_=0;
    vis[r]=1;
    for(int i=r-1;i>=l;i--){
        if(vis[nxt[i]]){
            op[i]=!op[nxt[i]],vis[i]=1;
            if(op[i]) cnt_++;
            else cnt++;
            while(1){
                while(vis[idx]) idx--;
                if(idx<i) break;
                op[idx]=!op[i],vis[idx]=1;
                if(op[idx]) cnt_++;
                else cnt++;
            }
        }
    }
    ans+=min(cnt,cnt_);
    return max(cnt,cnt_)-min(cnt,cnt_);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>a[i],p[i]={a[i],i};
        sort(p+1,p+n+1),cnt=0;
        for(int i=1;i<=n;i++){
            if(p[i].first==p[i-1].first){
                a[p[i].second]=a[p[i-1].second];
            }
            else a[p[i].second]=++cnt;
        }
        if(!check()){
            cout<<"No!\n";
            continue;
        }
        for(int i=1;i<=cnt;i++) t[i]=0;
        for(int i=n;i>=1;i--){
            nxt[i]=ask(a[i]),modi(a[i],i);
        }
        mx=0,la=1,ans=0;
        for(int i=1;i<=n;i++) w[i]=0;
        for(int i=1;i<=n;i++){
            mx=max(mx,nxt[i]);
            if(mx<=i) w[func(la,i)]++,la=i+1;
        }
        if(ans>n/2){cout<<"No!\n";continue;}
        if(ans==n/2){cout<<"Yes!\n";continue;}
        d=0,d[0]=1;
        for(int i=1;i<=n;i++){
            int k=1;
            while(w[i]>=k){
                int c=i*k;
                d=d|(d<<c);
                w[i]-=k,k*=2;
            }
            if(w[i]) d=d|(d<<w[i]),w[i]=0;
            if(d[n/2-ans]){
                cout<<"Yes!\n";
                break;
            }
            if(i==n) cout<<"No!\n";
        }
    }
    return 0;
}