题意:有一长度为\(n\)的序列,正向遍历,对于第\(i\)个元素,可以将其插入deque的队头或者队尾,问你最终得到deque后,逆序对最少是多少?

题解:假如将当前这个数插入队头,那么新增的逆序对就是\([2,len]\)中小于\(a[i]\)的个数,插入队尾也是同理,结合逆序对的求法,我们可以用线段树分别求出插入队头和队尾的贡献,取最小,然后update,具体看代码吧.

题解:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
int n;
vector<ll> all;
struct Node{
    int l,r;
    int cnt;
}tr[N<<4];
 
int get(int x){
    return lower_bound(all.begin(),all.end(),x)-all.begin()+1;
}
 
void push_up(int u){
    tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
}
 
void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,r,0};
        return;
    }
    tr[u]={l,r,0};
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}
 
void update(int u,int x){
    if(tr[u].l==tr[u].r){
        tr[u].cnt++;
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid) update(u<<1,x);
    else update(u<<1|1,x);
    push_up(u);
}
 
ll query(int u,int L,int R){
   if(tr[u].l>=L && tr[u].r<=R){
       return tr[u].cnt;
   } 
   int mid=(tr[u].l+tr[u].r)>>1;
   ll res=0;
   if(L<=mid) res+=query(u<<1,L,R);
   if(R>mid) res+=query(u<<1|1,L,R);
   return res;
}
 
int main() {
    int _;
    scanf("%d",&_);
    while(_--){
        all.clear();
        scanf("%d",&n);
        vector<ll> a(n+1);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
            all.pb(a[i]);
        }
        sort(all.begin(),all.end());
        all.erase(unique(all.begin(),all.end()),all.end());
        ll ans=0;
        build(1,0,(int)all.size()+1);
        for(int i=1;i<=n;++i){
            int now=get(a[i]);
            ll sum_l=query(1,0,now-1),sum_r=query(1,now+1,(int)all.size()+1);
            ans+=min(sum_l,sum_r);
            update(1,now);
        }
        printf("%lld\n",ans);
    }
    return 0;
}