What Goes Up Must Come Down
题意：
我们规定一个序列合理：当一个序列左部分是非降序列，右部分是非升序列（左右部分可为0，也就是整体可以为非降序列，非升序列）
题解：
树状数组来做 其实就是求左右的逆序对，我们枚举中简单i，然后区间[l,i]的逆序对和[i,r]的反向逆序对 详细可以看代码
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std
;
const int maxn
=5e6+10;
long long a
[maxn
],b
[maxn
],c
[maxn
],n
;
int lowbit(int x
){
return (-x
)&x
;
}
void modify(int pos
,int val
,long long c
[]){
for(int i
=pos
;i
<=maxn
+1;i
+=lowbit(i
))
c
[i
]+=val
;
}
long long query(int pos
,long long c
[]){
long long ret
=0;
for(int i
=pos
;i
>=1;i
-=lowbit(i
))
ret
+=c
[i
];
return ret
;
}
int ans1
[maxn
];
int ans2
[maxn
];
int main(){
scanf("%d",&n
);
for(int i
=1;i
<=n
;++i
)
scanf("%lld",&a
[i
]);
for(int i
=1;i
<=n
;++i
){
ans1
[i
]=query(maxn
-a
[i
]-1,a
);
modify(maxn
-a
[i
],1,a
) ;
}
for(int i
=n
;i
>=1;--i
){
ans2
[i
]=query(maxn
-a
[i
]-1,c
);
modify(maxn
-a
[i
],1,c
);
}
long long ans
=0;
for(int i
=1;i
<=n
;i
++){
ans
=ans
+min(ans1
[i
],ans2
[i
]);
}
cout
<<ans
;
return 0 ;
}
#include<stdio.h>
#include<string.h>
#include<iostream>
#include <algorithm>
using namespace std
;
typedef long long ll
;
int a
[100005],now
[100005],c
[100005];
int lowbit(int i
){return i
&-i
;}
int sum(int i
)
{
int ans
=0;
while(i
)
{
ans
+=c
[i
];
i
-=lowbit(i
);
}
return ans
;
}
void change(int i
)
{
while(i
<100005)
{
c
[i
]++;
i
+=lowbit(i
);
}
}
int main()
{
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)
scanf("%d",&a
[i
]);
ll ans
=0;
for(int i
=1;i
<=n
;i
++)
{
change(a
[i
]);
now
[i
]=i
-sum(a
[i
]);
}
memset(c
,0,sizeof(c
));
for(int i
=n
;i
>=1;i
--)
{
change(a
[i
]);
ans
+=min(now
[i
],n
-i
+1-sum(a
[i
]));
}
printf("%lld\n",ans
);
}
