当前位置: 首页 > news >正文

树状数组求逆序数原理_杂谈

谈一下树状数组怎么求逆序数,主要是记录用的,大家当乐子看就行

当得到一个数组,要求其逆序数时,人工最朴素的做法就是从前往后数,看这个数前面有多少个比它大的数,最终对这些结果求和就是整个数组的逆序数

使用树状数组的原理也是这个,一边从前往后遍历数组的位置,一边记录前面的数有多少个数比这个位置上的数字要小,这个位置的逆序数就是i-qry(pos),qry是查询从1到pos的数的出现有多少个数不大于当前位置的数

要做到这个实现,我们用树状数组维护这个过程,每遍历到一个数字,我们让在pos位置加1,并更新树状数组,然后查询1~pos

接下来又有一个小细节

  1. 如果数组中数字的出现不是连续的,比如说不是3 1 2 4这样出现的,而是100 10 20 4000这样出现的怎么办?

    ​ 我们进行离散化,输入数字时记录这个数的数值和位置,输入完之后根据数值进行排序,排序后的每个值位置依次变成1 2 3 . . . n。

上面这样处理对于重复大小的元素也能够正确处理,读者可以思考一下为什么

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5e5+5;
struct fac{int val,pos;
}a[N];
int b[N];
int tree[N];
int n;bool cmp(fac x,fac y){if(x.val==y.val) return x.pos<y.pos;return x.val<y.val;
}int lowbit(int x){return x&-x;}void ins(int p,int x){while(p<=n){tree[p]+=x;p+=lowbit(p);}
}int qry(int p){int ret=0;while(p>=1){ret+=tree[p];p-=lowbit(p);}return ret;
}void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].val;a[i].pos=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){b[a[i].pos]=i;}int ans=0;for(int i=1;i<=n;i++){ins(b[i],1);ans+=i-qry(b[i]);}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;
//	cin>>T;while(T--)solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=27012

相关文章:

  • 20232427 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 墨西哥证券交易所(BMV)等多个交易所股票数据API对接文档
  • Kubernetes技术详解-从理论到实践-(5)-控制器-Deployment - 详解
  • P5664 [CSP-S2019] Emiya 家今天的饭 题解
  • PWN手的成长之路-11-CISCN 2019华北 PWN1-栈溢出
  • sensitive-word:一个简单易用的敏感词过滤框架
  • 回归学习——包机制
  • vue 组件的常见8种通信方式
  • vue一键安装
  • 如何使用 ManySpeech 调用 SenseVoiceSmall 模型
  • 维基框架 (Wiki Framework) v1.1.2 | 企业级微服务开发框架
  • 国庆假期总结
  • CF1738E Balance Addicts
  • 2025浇注型聚氨酯厂家最新推荐榜:聚氨酯胶黏剂/聚氨酯胶辊/聚氨酯制品/聚氨酯原料/液体聚氨酯/聚氨酯浇注料/聚氨酯ABC料/浇筑聚氨酯/聚氨酯预聚物全场景实力厂家
  • C语言设计模式-策略模式
  • 动态张量运算自动优化技术解析
  • 【PhysUnits】15.9 引入P1后的右移运算(shr.rs) - 详解
  • 10. 模型与视图
  • [KaibaMath]1004 关于f(x,y) = [x]+[y] - [x+y]的平移稳定性
  • Mac OS 问题与技巧
  • 《算法设计与分析》第一章学习记录
  • nestjs 和 nextjs 分别是做啥的
  • 定时收集TCM数据并生成Excel报表并上传
  • 2025.10 国庆集训模拟赛总结
  • 详细介绍:https和http有什么区别-http各个版本有什么区别
  • CF2150F Cycle Closing
  • Easysearch 字段隐身之谜:source_reuse 与 ignore_above 的陷阱解析
  • QOJ856 Cactus 广义串并联图
  • CF2152 订题
  • 静态路由