题解：P14062 【MX-X21-T7】[IAMOI R5] 若我不曾见过太阳

· · 题解

若我不曾见过太阳题解

update:感谢 @Xiaohaoyu1020 指出本题解对于单调栈维护的错误。

这是一篇知更鸟推人的题解。

因为知更鸟，所以切了这道题，我的博客还有知更鸟赛的其他题解，欢迎来玩！

是一道思维好题呢。

首先，我们读懂题意后，通过手模样例发现排序与同剩余系相邻数之间的距离有关。

具体的说：对于下标为 i 和 j 的数，若 i \equiv j \pmod k 则 i 和 j 会在第 k 级排序中被交换。

发现到这里，我们距离答案就不远了，考虑交换两个数的意义是将一对逆序对恢复正序，考虑枚举分界点进行 0/1 染色。

对于分界点 x 将 \geq x 的数记为 1，将 < x 的数记为 0，对于这个分界点，它两侧的最近逆序对就是在这个分界点最后被调整为正序的逆序对，所有分界点中最后被调整的就是整体顺序前最后被调整的逆序对。

由于是顺序枚举分界点，每次只会修改一个数是 0 或者 1 且最近逆序对的左右端都是单调移动的，所以考虑单调栈维护即可。

最后，知更鸟可爱捏～

代码：

#include<bits/stdc++.h>
#define Robin 0
using namespace std;
const int N=4e6+10;
int st[N],top;
int a[N];
int len[N];
int n;

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    top=0;
    int ans=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        st[++top]=i;
        while(top && a[st[top]]<=i) top--;
        if(top) len[i]=st[top];
        else len[i]=0;
    }

    top=0;
    for(int i=n;i>=1;i--)
    {
        while(top && a[st[top]]>i) top--;
        if(top) len[i]=st[top]-len[i];
        if(len[i]>0) ans=min(ans,len[i]);
        st[++top]=i;
    }
    if(ans==INT_MAX) cout<<"0\n";
    else cout<<n-ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // freopen("text.in","r",stdin);
    // freopen("text.out","w",stdout);
    int T;
    cin>>T;
    while(T--) solve();
    return Robin;
}