poj 2299 树状数组求逆序数+离散化
数组 poj 树状 离散 求逆 序数
2023-09-14 09:08:12 时间
http://poj.org/problem?id=2299
最初做离散化的时候没太确定可是写完发现对的---由于后缀数组学的时候,,这样的思维习惯了吧
1、初始化as[i]=i;对as数组依照num[]的大小间接排序
2、bs[as[i]]=i;如今bs数组就是num[]数组的离散化后的结果
3、注意,树状数组中lowbit(i) i是不能够为0的,0&(-0)=0,死循环...
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const int MAXN = 500000 +100; int n; int C[MAXN],num[MAXN],as[MAXN],bs[MAXN],x[MAXN]; inline int lowbit(int i){return i&(-i);} void add(int i,int v) { for(;i<n;C[i]+=v,i+=lowbit(i));//printf("#i=%d#\n",i); } int sum(int i) { int s=0; for(;i>0;s+=C[i],i-=lowbit(i)); return s; } bool cmp(const int a,const int b) { return num[a]<num[b]; } int main() { //IN("poj2299.txt"); ll ans; while(~scanf("%d",&n) && n) { ans=0;CL(C,0);CL(x,0); for(int i=1;i<=n;i++) { scanf("%d",&num[i]); as[i]=i; } sort(as+1,as+1+n,cmp); for(int i=1;i<=n;i++) { bs[as[i]]=i; } ///////////////////// //for(int i=1;i<=n;i++) // printf("i=%d bs=%d\n",i,bs[i]); //////////////////////// for(int i=1;i<=n;i++) { add(bs[i],1); x[i]=sum(bs[i]-1); } for(int i=1;i<=n;i++) { ans+=sum(bs[i]-1)-x[i]; } printf("%lld\n",ans); } return 0; }
相关文章
- poj 3486 A Simple Problem with Integers(树状数组第三种模板改段求段)
- Java实现 LeetCode 532 数组中的K-diff数对(双指针,滑动窗口)
- Java实现 LeetCode 350 两个数组的交集 II(二)
- 集合的toArray方法产生的Object[]数组转换失败
- LeetCode - 53 最大子数组和
- C++每日面试之算法训练 寻找数组中最大值
- Leetcode 81. 搜索旋转排序数组 II
- c++ 找出一个数组中唯一一个出现2次的数字
- Java学习路线-3:数组
- Scala学习教程笔记一之基础语法,条件控制,循环控制,函数,数组,集合
- 二维数组和指向指针的指针
- POJ_1195 Mobile phones 【二维树状数组】
- 知识点1-树状数组[带poj Stars作为巩固]
- Python-OpenCV图像处理-02-numpy数组操作