正題

CF751E

---

題目大意

給你一個數(shù)組a和一個集合b，現(xiàn)在讓你把b中的數(shù)插入a，使得逆序對最少

---

解題思路

先計算a中的逆序對

對于b和a的逆序對，可以對數(shù)字進行排序，用線段樹存下放每個位置的最小代價，然后直接求最小值

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 1000100 #define mp make_pair #define fs first #define sn second using namespace std; ll t,n,m,w,x,nm,ans,c[N]; pair<ll,pair<ll,ll> >a[N<<2]; struct Tree {#define ls x*2#define rs x*2+1ll s[N<<2],lazy[N<<2];void push_up(ll x){s[x]=min(s[ls],s[rs]);return;}void get(ll x,ll y){s[x]+=y;lazy[x]+=y;return;}void push_down(ll x){if(lazy[x]){get(ls,lazy[x]);get(rs,lazy[x]);lazy[x]=0;}return;}void build(ll x,ll l,ll r){s[x]=0;lazy[x]=0;if(l==r)return;ll mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);return;}void add(ll x,ll L,ll R,ll l,ll r,ll y){if(L==l&&R==r){get(x,y);return;}push_down(x);ll mid=L+R>>1;if(r<=mid)add(ls,L,mid,l,r,y);else if(l>mid)add(rs,mid+1,R,l,r,y);else add(ls,L,mid,l,mid,y),add(rs,mid+1,R,mid+1,r,y);push_up(x);}ll ask(ll x,ll l,ll r,ll y){if(l==r)return s[x];push_down(x);ll mid=l+r>>1;if(y<=mid)return ask(ls,l,mid,y);else return ask(rs,mid+1,r,y);} }T; void add(ll x) {for(;x<=n;x+=x&-x)c[x]++;return; } ll ask(ll x) {ll sum=0;for(;x;x-=x&-x)sum+=c[x];return sum; } int main() {scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&m);w=0;nm=n+1;ans=0;T.build(1,1,nm);for(ll i=1;i<=n;++i){c[i]=0;scanf("%lld",&x);T.add(1,1,nm,i+1,nm,1);a[++w]=mp(x,mp(0,i));a[++w]=mp(x,mp(1,i));//相同的數(shù)字不計逆序對}for(ll i=1;i<=m;++i){scanf("%lld",&x);a[++w]=mp(x,mp(1,0));}sort(a+1,a+1+w);for(ll i=1;i<=w;++i){if(!a[i].sn.fs){T.add(1,1,nm,a[i].sn.sn+1,nm,-1);ans+=ask(n)-ask(a[i].sn.sn);//計算a中的貢獻add(a[i].sn.sn);}else if(!a[i].sn.sn){ans+=T.s[1];}else{T.add(1,1,nm,1,a[i].sn.sn,1);}}printf("%lld\n",ans);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的【线段树】Optimal Insertion（CF751E）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。