题解：CF1951F Inversion Composition

Caiest_Oier · 2024-04-12 21:19:38 · 题解

CF1951F

把式子写清楚，就是要你构造一个排列 q，满足 \sum_{i=1}^{n}\sum_{j=i+1}^{n}[q_i>q_j]+[q_{p_i}>q_{p_j}]=k。

令 invp_{p_i}=i，即 p 的逆排列。对于一对 (i,j) 满足 i<j，如果 invp_i>invp_j，则其贡献固定为 1，否则如果 q_i<q_j，贡献为 0，q_i>q_j，贡献为 2。这里大概的思路就是把两种逆序对的求和方式做一个匹配，对于 invp_i>invp_j 的对，则两边必定恰有一个满足，否则要么两个都不满足或都满足（可能有点抽象但是我也不知道该怎么表达了）。

对于贡献固定为 1 的对，可以通过计算逆序对的方式把这部分贡献减掉。如果剩下的 k 不是偶数，则必定无解。否则从前往后构造，每次加入的 q 都是最小的，贡献最多的逆序对。如果 k 比这些逆序对少，则将当前元素适当升高，把 k 减到 0，后面全部往大了加，不贡献逆序对即可。如果最后 k>0 则还是无解，否则输出答案即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,p[1000003],invp[1000003],q[1000003],lft,rgt;
int lowbit(int X){return (X&(-X));}
class BIT{
    public:
        int TreeAr[1000003];
        void modify(int wz,int val){
            wz++;
            for(int i=wz;i<=1000000;i+=lowbit(i))TreeAr[i]+=val;
            return;
        }
        int Query(int l,int r){
            l++;
            r++;
            int ret=0;
            for(int i=r;i;i-=lowbit(i))ret+=TreeAr[i];
            for(int i=l-1;i;i-=lowbit(i))ret-=TreeAr[i];
            return ret;
        }
}T;
int stk[500003],tot;
signed main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>p[i];
            invp[p[i]]=i;
        }
        for(int i=0;i<=n+10;i++)T.TreeAr[i]=0;
        for(int i=1;i<=n;i++){
            k-=T.Query(invp[i]+1,n);
            T.modify(invp[i],1);
        }
        if(k<0||k%2!=0){
            cout<<"NO\n";
            continue;
        }
        k/=2;
        for(int i=0;i<=n+10;i++)T.TreeAr[i]=0;
        T.modify(invp[1],1);
        lft=rgt=0;
        q[1]=0;
        for(int i=2;i<=n;i++){
            if(T.Query(1,invp[i]-1)<=k){
                k-=T.Query(1,invp[i]-1);
                lft--;
                q[i]=lft;
            }
            else{
                if(k==0){
                    for(int j=i;j<=n;j++)q[j]=rgt+(j-i+1);
                    break;
                }
                tot=0;
                for(int j=1;j<i;j++){
                    if(invp[j]<invp[i])stk[++tot]=q[j];
                }
                sort(stk+1,stk+tot+1);
                q[i]=stk[tot-k]+1;
                for(int j=1;j<i;j++)if(q[j]>stk[tot-k])q[j]++;
                rgt++;
                k=0;
            }
            T.modify(invp[i],1);
        }
        if(k>0){
            cout<<"NO\n";
            continue;
        }
        cout<<"YES\n";
        for(int i=1;i<=n;i++)cout<<q[i]-lft+1<<" ";
        cout<<endl;
    }
    return 0;
}