# Bzoj4240: interesting family garden (tree array)

2020-12-07 14:36:29

solution ：
The subscript of the original array is 1~n.
After disruption, the number of exchanges is in reverse order .
Because one exchange will produce a reverse pair ..
The number of pairs in reverse order should be as small as possible .

It's about a mountain ？
It's something that's high in the middle and diminishing on both sides .
So sort by height .
Look at whether the insertion on the left or on the right produces fewer reverse pairs .
Greed

Code implementation ：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
struct node {

int id,x;}a[310000];int s[310000];
int lowbit(int x) {

return x&-x;}int n;
void change(int x) {

while(x<=n) {s[x]++;x+=lowbit(x);}}
int find_sum(int x) {

int ans=0;while(x>0){ans+=s[x];x-=lowbit(x);}return ans;}
bool cmp(node n1,node n2) {

return n1.x>n2.x;}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){

scanf("%d",&a[i].x);a[i].id=i;}
sort(a+1,a+1+n,cmp);ll ans=0;memset(s,0,sizeof(s));
for(int i=1;i<=n;) {
int x=i;
for(;x<=n;x++) {
int t=find_sum(a[x].id);ans+=min(t,i-1-t);
if(a[x].x!=a[x+1].x)break;
}
for(;i<=x;i++)change(a[i].id);
}printf("%lld\n",ans);
return 0;
}

https://chowdera.com/2020/12/202012071434170659.html