逆序对模板
发布日期:2021-11-02 09:48:59
浏览次数:2
分类:技术文章
本文共 2265 字,大约阅读时间需要 7 分钟。
逆序对
摘自百度并进行了部分修改。
归并排序
#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月10日 23时28分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
input js number 整数_JS基础简单小结(1)
2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导
2019-04-21
mysql 阿里云 添加磁盘空间_rds 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
lsof查看占用高_lsof解决磁盘占用过高,查询却无大文件处理一例!
2021-06-24