Codeforces1579 E2. Array Optimization by Deque（贪心+逆袭对）

考虑每个数与前面已加入的数的贡献,
如果当前数x放在左边,那么贡献为前面x的数的数量.

这样的做法不需要当前数的摆放对之后的数的影响,
因为对于逆序对(x,y)的两个数x和y,我们的做法保证了一定是'新出现的数'对'旧出现的数'计算贡献,
只会计算一次且不会遗漏.

#include
#define MULTI_CASE
#define PI pair
#define int long long
using namespace std;
const int maxm=2e6+5;
const int BIT_maxm=2e6+5;
struct BIT{
   int c[BIT_maxm];
   inline int lowbit(int i){return i&-i;}
   void add(int i,int t){while(i>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int num=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+num,a[i])-b;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        T.add(a[i],1);
        int l=T.ask(a[i]-1);
        int r=i-T.ask(a[i]);
        ans+=min(l,r);
    }
    cout<>T;while(T--)
    #endif
    solve();
}
void Init(){
    ios::sync_with_stdio(0);cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("../in.txt","r",stdin);
    freopen("../out.txt","w",stdout);
    #endif
}
signed main(){
    Init();
    Main();
    return 0;
}