Asia Yokohama Regional Contest 2018 G题 What Goes Up Must Come Down
2024-10-11 20:15:40
链接 G题 https://codeforces.com/gym/102082
使其成为单峰序列需要交换多少次相邻的数。
树状数组维护逆序对。
对于每个序列中的数,要么在单峰的左侧,要么在单峰的右侧,所以从左边开始维护每个数相对于左侧的逆序对数量,从右边开始维护每个数相对于右侧的逆序对数量。取小加入答案即可。
#include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << x << endl
using namespace std;
typedef long long ll;
const int MAXN=1e5+;
const int INF=0x3f3f3f3f;
const int MOD=1e9+;
int a[MAXN],L[MAXN],R[MAXN]; struct BIT
{
int c[MAXN];
void init() {memset(c,,sizeof(c));}
int lowbit(int x) {return x&(-x);}
void add(int i,int x)
{
while(i<MAXN)
{
c[i]+=x;
i+=lowbit(i);
}
}
ll sum(int i)
{
ll res=;
while(i)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
}tree; int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n;
cin>>n;
for(int i=;i<=n;++i) cin>>a[i];
for(int i=;i<=n;++i)
{
tree.add(a[i],);
L[i]=i-tree.sum(a[i]);
}
tree.init();
for(int i=n;i>=;--i)
{
tree.add(a[i],);
R[i]=n-i+-tree.sum(a[i]);
}
ll ans=;
for(int i=;i<=n;++i)
ans+=min(L[i],R[i]);
cout<<ans<<endl;
return ;
}
最新文章
- ASP.NET Core开发-如何配置Kestrel 网址Urls
- Socket通讯实例-基本Socket
- win7(64位)php5.5-Apache2.4-mysql5.6环境安装
- PHP $_FILES中error返回值详解
- Angularjs 的 ngInfiniteScroll 的使用方法
- PotPlayer为播放而生的专业播放器
- Android Studio 项目代码全部消失--出现原因及解决方法
- linux下使用go-oci8
- UTF编码问题小结
- MongoDB 权限 验证
- POJ 2411 Mondriaan&#39;s Dream
- UVa 11729 - Commando War(贪心)
- 给EasyUI的DateBox控件添加清除button
- fastjson将json格式null转化空串
- css中auto的用法
- JaveScript简单数据类型(JS知识点归纳二)
- motan负载均衡/zookeeper集群/zookeeper负载均衡的关系
- Kali Linux安装Google中文输入法(只需5步)
- asp.netajax与jquery和bootstrap的无刷新完美实现
- Java 接口篇
热门文章
- 整理了2019年上千道Java面试题,近500页文档,用了1个月时间!
- Web基础了解版03-jQuery
- Codeforces Round #599 (Div. 2)
- So Easy - 在Linux服务器上部署 .NET Core App
- Java 异常规范
- C# dictionary to bytes and bytes convert to dictionary
- 百度大脑UNIT3.0详解之嵌入式对话理解技术
- 2019年Java面试题基础系列228道(3)
- 非常详细的 (VMware安装Centos7超详细过程)
- 查看python版本多少位的