Codeforces Round #744 (Div. 3) E2. Array Optimization by Deque (贪心,逆序对)

Codeforces Round #744 (Div. 3) E2. Array Optimization by Deque  (贪心,逆序对)

  • 题意:有一长度为\(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;
    }
    
上一篇:Codeforces Round #744 (Div. 3)


下一篇:Caused by: com.mysql.cj.exceptions.InvalidConnectionAttributeException: The server time zone value &