CF1579E2(CF1579E2)

题意:

顺序操作一个长度为 \(n\) 的序列 \(a_i\) ,每次可以选择将第 \(i\) 个放到一个初始为空的双端队列的最前或最后,希望进行完 \(n\) 次操作后逆序对数量最小化。

思路:

考虑贪心地放,每次计算放在最前或最后会增加的逆序对数量,选择较小的放置;

这个贪心的正确性显然,如果第 \(i+1\) 个放前面,则无论如何第 \(i\) 个都在第 \(i+1\) 个以后,反之如果第 \(i+1\) 个放在最后,则第 \(i\) 个一定在其之前,所以前一个的怎么放对后面的贡献都相同,放最好的就行;

求逆序对就数据结构维护一下修改和查询排名,我写的离散化后线段树。

代码:

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,a[(int)(2e5+10)],t[(int)(1e6+10)],b[(int)(2e5+10)];
void add(int u,int st,int ed,int id,int k)
{
    if(st==ed) 
    {
        t[u]+=k;
        return ;
    }
    int mid=(st+ed)>>1;
    if(mid>=id) add(u*2,st,mid,id,k);
    else add(u*2+1,mid+1,ed,id,k);
    t[u]=t[u*2]+t[u*2+1];
}
int sum(int u,int st,int ed,int l,int r)
{
    if(l<=st&&r>=ed) return t[u];
    if(l>ed||r<st) return 0;
    int mid=(st+ed)>>1;
    return sum(u*2,st,mid,l,r)+sum(u*2+1,mid+1,ed,l,r);
}
signed main()
{
    int q;cin>>q;
    while(q--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
        // for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        // puts("");
        int ans=0;
        memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++)
        {
            int cnt1=sum(1,1,n,a[i]+1,n),cnt2=sum(1,1,n,1,a[i]-1);
            ans+=min(cnt1,cnt2);
            add(1,1,n,a[i],1);
        }
        cout<<ans<<"\n";
    }
}
————————

Meaning:

A sequence \ (a_i \) with a length of \ (n \) is operated sequentially. You can choose to put the \ (I \) at the front or last of a double ended queue that is initially empty each time. You want to minimize the number in reverse order after \ (n \) operations.

Idea:

Consider greedy placement, and select a smaller placement for the number of pairs in reverse order that will increase when placed first or last in each calculation;

The correctness of this greed is obvious. If the \ (I + 1 \) is placed first, then in any case, the \ (I \) is after the \ (I + 1 \). On the contrary, if the \ (I + 1 \) is placed last, then the \ (I \) must be before it. Therefore, the contribution of the former to the later is the same, and the best one is OK;

Find the reverse order. Maintain the modification and query ranking of the data structure. I wrote the discretized line segment tree.

code:

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,a[(int)(2e5+10)],t[(int)(1e6+10)],b[(int)(2e5+10)];
void add(int u,int st,int ed,int id,int k)
{
    if(st==ed) 
    {
        t[u]+=k;
        return ;
    }
    int mid=(st+ed)>>1;
    if(mid>=id) add(u*2,st,mid,id,k);
    else add(u*2+1,mid+1,ed,id,k);
    t[u]=t[u*2]+t[u*2+1];
}
int sum(int u,int st,int ed,int l,int r)
{
    if(l<=st&&r>=ed) return t[u];
    if(l>ed||r<st) return 0;
    int mid=(st+ed)>>1;
    return sum(u*2,st,mid,l,r)+sum(u*2+1,mid+1,ed,l,r);
}
signed main()
{
    int q;cin>>q;
    while(q--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
        // for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        // puts("");
        int ans=0;
        memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++)
        {
            int cnt1=sum(1,1,n,a[i]+1,n),cnt2=sum(1,1,n,1,a[i]-1);
            ans+=min(cnt1,cnt2);
            add(1,1,n,a[i],1);
        }
        cout<<ans<<"\n";
    }
}