CF1579E2(CF1579E2)-其他

CF1579E2(CF1579E2)

代码：

``````#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;
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);
}
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;
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);