逆序对模板
发布日期:2021-11-02 09:48:59 浏览次数:2 分类:技术文章

本文共 2265 字,大约阅读时间需要 7 分钟。

逆序对

摘自百度并进行了部分修改。

归并排序
#include 
using namespace std;// [l, r)void merge_inversion(vector
&nums, int l, int r, int &cnt) {
cout << l << " - " << r << endl; // 只有一个元素直接返回 if (r - l <= 1) return; // 分治 int m = l + (r - l) / 2; merge_inversion(nums, l, m, cnt); merge_inversion(nums, m, r, cnt); // 归并, 按照从大到小的顺序。 int i = l; int j = m; vector
temp; for (int k = l; k < r; ++k) {
if (i < m && j < r) {
if (nums[i] > nums[j]) {
cnt += (r - j); temp.push_back(nums[i++]); } else {
temp.push_back(nums[j++]); } } else {
if (i < m) {
temp.push_back(nums[i++]); } else if (j < r) {
temp.push_back(nums[j++]); } } } for (int k = l; k < r; ++k) {
nums[k] = temp[k - l]; }}int main() {
vector
nums = {
1, 7, 2, 5, 8, 10, 6}; int ans = 0; merge_inversion(nums, 0, nums.size(), ans); cout << ans << endl; for (int i = 0; i < nums.size(); ++i) {
cout << nums[i] << " "; } cout << endl; return 0;}
树状数组
#include 
#include
#include
#include
#define ll long longusing namespace std;const int maxn = 1e6 + 10;ll n, m, A[maxn], B[maxn], ans, L[maxn];struct BIT {
ll tree[maxn]; ll lowbit(ll x) {
return x & -x; } void update(ll pos, ll val) {
while (pos <= n) {
tree[pos] += val; pos += lowbit(pos); } } ll query(ll pos) {
ll res = 0; while (pos) {
res += tree[pos]; pos -= lowbit(pos); } return res; }} T;int Search(ll x) {
return lower_bound(B + 1, B + 1 + m, x) - B;}int main() {
scanf("%lld", &n); for (int i = 1; i <= n; i++) {
scanf("%lld", &A[i]), B[i] = A[i]; } sort(B + 1, B + 1 + n); m = unique(B + 1, B + 1 + n) - B - 1; for (int i = 1; i <= n; i++) {
A[i] = Search(A[i]); T.update(A[i], 1); L[i] = i - T.query(A[i]); ans += L[i]; } printf("%lld", ans); return 0;}

转载地址:https://blog.csdn.net/weixin_43820352/article/details/111500432 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:51nod 1685 第K大区间2(树状数组,逆序对)
下一篇:51nod 1693 水群(思维,最短路,spfa)

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月10日 23时28分08秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

input js number 整数_JS基础简单小结(1) 2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导 2019-04-21
docker mysql服务启动失败_docker中mysql初始化及启动失败问题解决方案 2019-04-21
mysql 阿里云 添加磁盘空间_rds mysql磁盘空间包含 2019-04-21
mysql 1364 hy000_mysql SQL Error: 1364, SQLState: HY000 保存错误 2019-04-21
mysqli拓展还能用mysql_最近在学习php,其中使用了MYSQLi扩展,注意是MYSQLi不是MYSQL(因PHP7已经不支持MYSQL扩展了)。... 2019-04-21
java中gui_java中GUI是什么意思?详细图解 2019-04-21
java iso 8601_如何在iOS上获得ISO 8601日期? 2019-04-21
windows8怎么下载python_win8怎么安装python 2019-04-21
linux猜数字程序,用linux实现猜数字小游戏源码 2019-04-21
linux下堆栈溢出实例,堆栈溢出在Linux上沉默? 2019-04-21
python创建nc文件_工具箱第2期 用python玩转NC 2019-04-21
拆分文件_文件拆分与合并 2021-06-24
开发优势_小程序开发优势好处有哪些 2021-06-24
4光影补丁_我的世界seus光影包 2021-06-24
aria手机下载_Aria2App 2021-06-24
汇编指令msr_ARM汇编:MRS和MSR指令 2021-06-24
慕课python第五周测试答案_中国大学MOOC(慕课)_python+_满分章节测试答案 2021-06-24
lsof查看占用高_lsof解决磁盘占用过高,查询却无大文件处理一例! 2021-06-24
python调用oracle过程 权限不足_oracle-存储过程提示 ORA-01031: 权限不足 2021-06-24