题解：P9843 [ICPC 2021 Nanjing R] Paimon Sorting

· · 题解

感谢喵仔牛奶的数据喵喵喵。

对于这种每次添加一个数的询问，我们先不考虑加数，仅考虑调用一次该函数。

首先，第一次循环会把整个序列中最大的数丢到最前面。

然后第一次操作的交换次数可以暴力计算。

考虑第二次以及后面的所有循环。假设我们现在是第 i 次循环，显然 1 到 i-1 已经按照小到大排序了，然后我们会把 i 前面的每种数和这个位置进行一次交换。这个种类个数我们用树状数组直接维护即可。

那么答案我们就可以 O(n\log n) 快速计算了啊。

接下来考虑加入一个数对答案的影响。

分类讨论下，如果这个数字比前面的最大值小或者等于，那么这个数字只会在最后一个循环用到，然后贡献就是前面的比它大的数的种类个数。

如果这个数字比最大值大。假设现在序列总长度为 n。

那么第一次循环这个东西会被交换到最前面。操作次数加一。

然后最后一个数会变成之前的最大值。贡献就是还是一。

然后第 2 到 n-1 次循环需要分类讨论下，如果说 1 到 n-1 最大值只有一个，那么前面 n-1 个数之间的相对大小并没有改变，贡献不会增加。

若最大值有两个以上，假设第二个最大值位置在 p，那么发现从 p 到 n-1 中的每个位置，循环到这个位置时，比他大是数字的种类个数会多一个，所以贡献是 n-p。

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=1e5+5;
int t,n,a[N],tree[N],cnt[N];
il int lowbit(int x){
    return x&(-x);
}
bool vis[N];
int query(int x){
    int re=0;
    while(x){
        re+=tree[x];x-=lowbit(x);
    }return re;
}
void update(int x,int w){
    if((w==1&&!vis[x])||(w==-1&&vis[x]==1)){
        vis[x]=(w!=-1);
        while(x<=n){
            tree[x]+=w;x+=lowbit(x);
        }
    }
}
int maxx=0;ll ans,ma,po1,po2;
int main(){
    read(t);
    while(t--){
        read(n);for(int i=1;i<=n;i++)read(a[i]);po1=po2=0;
        ans=0;ma=a[1];update(a[1],1);cnt[a[1]]++;
        printf("0");
        for(int i=2;i<=n;i++){
            update(a[i],1);cnt[a[i]]++;
            if(a[i]>ma){
                ans++;ans+=query(n)-query(ma);
                if(po2)
                ans+=i-po2;
                ma=a[i];po1=i;po2=0;
            }else{
                ans+=query(n)-query(a[i]);if(a[i]==ma)if(po2==0)po2=i;
            }
            printf(" %lld",ans);
        }
//      cout<<query(n)<<endl;
        if(t!=0)puts("");
        for(int i=1;i<=n;i++)update(a[i],-1),cnt[i]--;
    }
    return 0;
}