P11158 【MX-X6-T4】夢重力 题解

P11158 【MX-X6-T4】夢重力

分类讨论好题。

不难发现交换行等价于交换列，考虑转化贡献体，枚举长度为 \frac{n}{2} 区间，统计这个区间被多少种交换方式包含。

考虑一个长度为 \frac{n}{2} 区间满足要求的充要条件是存在一段空权值区间 [x,x+\frac{n}{2}] 使得区间中所有 p_i 不属于 [x,x+\frac{n}{2}]。注意到如果存在满足要求的区间则其余每一行都必然有数，且上边界必然在 [\frac{n}{2}+1,n]，下边界必然在 [1,\frac{n}{2}]，所以我们维护 [1,\frac{n}{2}] 中的最大值和 [\frac{n}{2}+1,n] 中的最小值即可判定是否存在满足要求的区间。可以使用 set 维护。

如果这个区间本身就满足要求，那么在区间内部交换或区间外部交换没有影响，对答案贡献 \frac{\frac{n}{2}\times(\frac{n}{2}-1)}{2}\times 2=\frac{n}{2}\times(\frac{n}{2}-1)。但是如果 [1,\frac{n}{2}] 中有数，我们可以把 [1,\frac{n}{2}] 中的最大值换成一个较小的上边界，同样满足条件。如果 [\frac{n}{2}+1,n] 中有数同理。需要特判一下。

如果这个区间本身不满足要求，还是有可能通过交换得到满足要求的区间。不难发现此时一定是换掉 [1,\frac{n}{2}] 中的最大值或 [\frac{n}{2}+1,n] 中的最小值，于是我们分别计算一下换掉之后的区间大小即可。注意如果换掉之后空权值区间长度大于 \frac{n}{2}，则有两种换法，如果空权值区间长度等于 \frac{n}{2}，则只有一种换法。这个结论手玩一下不难发现。

然后就做完了，时间复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
long long n,a[500000],cs=0,cb=0,ans=0;
set<long long>q;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    q.insert(0),q.insert(n+1);
    for(int i=1;i<=n/2;i++)q.insert(a[i]);
    for(int i=1;i<=n/2+1;i++)
        {
        set<long long>::iterator mx=q.lower_bound(n/2+1),mi=q.upper_bound(n/2),tmp=mx;
        mi--;
        if((*mx)-(*mi)-1>=n/2)
           {
           ans+=(n/2)*(n/2-1);
           if((*mx)!=n+1)ans++;
           if((*mi)!=0)ans++;
           }
        else
            {
            mx++;
            if((*mx)-(*mi)-1>n/2)ans+=2;
            else if((*mx)-(*mi)-1==n/2)ans++;
            mx=tmp,mi--;
            if((*mx)-(*mi)-1>n/2)ans+=2;
            else if((*mx)-(*mi)-1==n/2)ans++;
            }
        q.insert(a[i+n/2]),q.erase(a[i]);
        }
    printf("%lld\n",ans);
    return 0;
}