Solution：P5972 [PA 2019] Desant

Argon_Cube · 2025-12-08 14:43:31 · 题解

模拟赛 T1。这个复杂度虽然比正解劣但是跑的挺快的，原题和模拟赛都过了。

看到 n\leq 40 考虑 Meet in the Middle。但是显然把序列折半和把值域折半都没啥前途。

考虑我们的折半在干什么。把排列放到平面上变成 n 个点 (i,p_i)，按序列折半相当于把平面切成左右两半，按值域折半相当于切成上下两半。那么，既然切一刀是没有前途的，我们不妨切两刀：

像上图一样，我们把平面切成四块，两块黑区两块白区。因为给的是个排列，所以显然一个白区加一个黑区里面最多有 \frac n2 个点。此时可以把逆序对 ((i,a_i),(j,a_j)) 分成几类：

考虑枚举两个黑区内的每个点选不选。因为两个白区不会相互贡献，它们基本上独立了，我们可以分开枚举这两个白区内的点选不选，只需要记一下选了几个点就能简单合并。

这样的复杂度显然还是 \Omicron(2^n) 的，把点全放黑区就炸了。但是我们同样还可以枚举白区然后分开枚举黑区，把这两个暴力拼起来我们就能得到 \Omicron(2^{\frac {3n}4}) 的优秀复杂度，做完了。

这个复杂度不难证明。考虑如果一块有 m 个点，那么与它相邻的两块最多各有 \frac n2-m 个点，总共只有 n-m 个点。显然一定有一块的 m\geq \frac n4，我们把那一块所属的区域分开枚举就是 \Omicron(2^{n-m})=\Omicron(2^{\frac 34n}) 的。

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>

#define rgall(arr)          (arr).begin(),(arr).end()
#define rgo1(arr,cnt)       (arr).begin()+1,(arr).begin()+1+(cnt)
#define rgcnt(arr,cnt)      (arr).begin(),(arr).begin()+(cnt)
#define rgany(arr,rgl,rgr)  (arr).begin()+(rgl),(arr).begin()+(rgr)
#define fori(i,a,b)         for(int i=(a);i<=(b);i++)
#define ford(i,a,b)         for(int i=(a);i>=(b);i--)
#define fori0(i,a,b)        for(int i=(a);i<(b);i++)
#define ford0(i,a,b)        for(int i=(a);i>(b);i--)
#define fr first
#define sc second

using namespace std;

struct val
{
    int a;
    long long b;
    val operator+(val c)const
    {
        if(c.a==a)
            return (val){a,b+c.b};
        return a<c.a?*this:c;
    }
    val operator*(val c)const
    {
        return (val){a+c.a,b*c.b};
    }
};

array<array<vector<pair<int,int>>,2>,2> vp,vb/*in{inv,count}*/;
vector<vector<int>>                     vl,vr,vu,vd;//adj
array<val,41>                           ans0,ans1,ans;
array<int,41>                           va;
constexpr val                           inf{10000};

void solve(int ax,int ay,int bx,int by,decltype(vd)& vc)
{
    auto& a=vp[ax][ay],& b=vp[bx][by];
    vc=vector<vector<int>>(1<<a.size(),vector<int>(1<<b.size()));
    fori0(i,0,a.size())
        fori0(j,0,b.size())
            vc[1<<i][1<<j]=(a[i].fr>b[j].fr)^(a[i].sc>b[j].sc);
    fori0(i,1,1<<a.size())
        fori0(j,1,1<<b.size())
            if(j&j-1)
                vc[i][j]=vc[i][j^(j&-j)]+vc[i][j&-j];
            else if(i&i-1)
                vc[i][j]=vc[i^(i&-i)][j]+vc[i&-i][j];
}
void solve0(int n)//max at x=y
{
    solve(0,1,0,0,vl),solve(1,0,0,0,vd),solve(0,1,1,1,vu),solve(1,0,1,1,vr);
    auto& a=vb[0][1],& b=vb[1][0],& c=vb[0][0],& d=vb[1][1];
    int cc=vp[0][0].size(),cd=vp[1][1].size();
    // cerr<<a.size()<<' '<<b.size()<<' '<<c.size()<<' '<<d.size()<<'\n';
    fori0(i,0,a.size())
        fori0(j,0,b.size())
        {
            ans0.fill(inf),ans1.fill(inf);
            fori0(k,0,c.size())
                ans0[c[k].sc]=ans0[c[k].sc]+(val){vl[i][k]+vd[j][k]+c[k].fr,1};
            fori0(k,0,d.size())
                ans1[d[k].sc]=ans1[d[k].sc]+(val){vu[i][k]+vr[j][k]+d[k].fr,1};
            fori(k,0,cc)
                fori(l,0,cd)
                {
                    val& aa=ans[k+l+a[i].sc+b[j].sc],bb=ans0[k]*ans1[l];
                    bb.a+=a[i].fr+b[j].fr+a[i].sc*b[j].sc,aa=aa+bb;
                }
        }
}
void solve1(int n)
{
    solve(0,0,0,1,vl),solve(0,0,1,0,vd),solve(1,1,0,1,vu),solve(1,1,1,0,vr);
    auto& a=vb[0][0],& b=vb[1][1],& c=vb[0][1],& d=vb[1][0];
    int cc=vp[0][1].size(),cd=vp[1][0].size();
    // cerr<<a.size()<<' '<<b.size()<<' '<<c.size()<<' '<<d.size()<<'\n';
    fori0(i,0,a.size())
        fori0(j,0,b.size())
        {
            ans0.fill(inf),ans1.fill(inf);
            fori0(k,0,c.size())
                ans0[c[k].sc]=ans0[c[k].sc]+(val){vl[i][k]+vu[j][k]+c[k].fr,1};
            fori0(k,0,d.size())
                ans1[d[k].sc]=ans1[d[k].sc]+(val){vd[i][k]+vr[j][k]+d[k].fr,1};
            fori(k,0,cc)
                fori(l,0,cd)
                {
                    val& aa=ans[k+l+a[i].sc+b[j].sc],bb=ans0[k]*ans1[l];
                    bb.a+=a[i].fr+b[j].fr+k*l,aa=aa+bb;
                }
        }
}

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    fori(i,1,n)
    {
        cin>>va[i];
        vp[i<<1>n][va[i]<<1>n].emplace_back(i,va[i]);
    }
    fori(i,0,1)
        fori(j,0,1)
        {
            auto& a=vp[i][j],& b=vb[i][j];
            int m=a.size();
            b.resize(1<<m);
            fori0(k,3,1<<m)
            {
                if(!(k&k-1))
                    continue;
                int l=0;
                while(!(k&1<<l))
                    ++l;
                b[k]=b[k^1<<l];
                fori0(ii,l+1,m)
                    if(k&1<<ii)
                        b[k].fr+=(a[l].fr>a[ii].fr)^(a[l].sc>a[ii].sc);
            }
            fori0(k,0,1<<m)
                b[k].sc=__builtin_popcount(k);
        }
    ans.fill(inf),ans0=ans1=ans;
    // solve0(n);
    max(vp[0][1].size(),vp[1][0].size())<max(vp[0][0].size(),vp[1][1].size())?solve0(n):solve1(n);
    fori(i,1,n)
        cout<<ans[i].a<<' '<<ans[i].b<<'\n';
    return 0;
}