2021 icpc南京站 D - Paimon Sorting（主席树+打表）

题意为给定一种排序方式 如图

问对于指定数组的每一个前缀，派蒙的排序方法要交换多少次

样例： 

我们可以先把他的排序方式抄下来，讲每一层输出出来试着找找规律

先试着把每层得到的数列输出出来

可以很明显的看到，在第i层排序中，会将第i大的元素排在第一位，并将比i大的所有元素全部排好序

而他问对于每一个前缀，我们可以直接打表找下规律，看和有没有什么关系

如果找到了和之间的关系，那么我们可以考虑使用数据结构，一个个把数插进去求解

其中最好找出规律的是当

可以很明显答案等于加上前i-1个元素中，比大的有几个数（去重）

而在当时

答案就等于res[i-1]

以上两种情况直接主席树维护，把数按顺序插进去即可

最难打表打出来的是当时

这里如果仅通过打表很容易误判成直接+2

因为这里并不是前i-1中最大值贡献的2次交换，而是前i-1中最大值出现第二次之后每个数也都额外贡献了交换

比如前i-1是   1 2 3 4 4 3

这里加个5进来   答案是res[i-1]+2+sum（4，3）=res[i-1]+4次

仔细思考一下排序方式就可以理解

当然也可以暴力打表

眼神好没什么是不可能的

代码如下：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et  cout<<'\n'
#define xx first
#define yy second
#define ld long double
using namespace std;
const int N = 2e6+100;
int tree[N];
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
void add(int l, int r, int v, int x,int val){
    if (l == r){
        tree[v]+=val;
        tree[v] = min(1ll,tree[v]);
        tree[v] = max(tree[v],0ll);
        return ;
    }
    else{
        int mid = (l + r) >> 1;
        if (x <= mid) add(l, mid, v << 1, x,val);
        else add(mid + 1, r, v << 1 | 1, x,val);
        tree[v] = tree[v << 1] + tree[v << 1 | 1];
    }
}
int query(int v,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr){
        return tree[v];
    }
    int sum = 0;
    int mid = (l+r)>>1;
    if(ql<=mid)
        sum += query(v<<1,l,mid,ql,qr);
    if(qr>=mid+1)
        sum += query(v<<1|1,mid+1,r,ql,qr);
    return sum;
}
int a[N];
vector<int> res;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        input(n);
        int mx = -1;
        int last = 0;
        int tmp = 0,cnt = 0;
        fer(i,1,n){
            input(a[i]);
            if(i==1){
                res.push_back(last);
                mx = a[i],cnt = 1;
            }
            else{
                if(a[i]==mx){
                    res.push_back(last);
                    cnt++;
                    if(cnt>=2) tmp++;
                }
                else if(a[i]<mx){
                    last = last+ query(1,1,n,a[i]+1,n);
                    res.push_back(last);
                    if(cnt>=2) tmp++;
                }
                else{
                    last = last+2+tmp;
                    res.push_back(last);
                    mx = a[i];
                    tmp = 0;
                    cnt = 1;
                }
            }
            add(1,n,1,a[i],1);
        }
        for(int i=1;i<=n;i++){
            add(1,n,1,a[i],-1);
            if(i==n){
                cout<<res[i-1];
                break;
            }
            cout<<res[i-1]<<" ";
        }
        cout<<'\n';
        res.clear();
    }
}