题目见洛谷
分析:首先,这道题需要进行一次排序,题目中没有给出数据范围,但是实测需要使用离散化。。//话说离散化真的好烦人啊。。(雾。。
其次,我认为这道题是可以用线段树做的!!!//虽然我没写出来,代码太冗长了(雾。。
总之,还是膜了一发二叉索引树,发现这种神奇的算法真的是太神奇了! 我真的很佩服这个算法的发明者的智商,方法实在太巧妙了。@Peter M. Fenwick
简单介绍一下这个算法:利用二叉树(废话,名字都是二叉索引树。。)进行数据的存储及维护,巧妙地利用补码表示法和二进制数据的特点,进行节点的定位,成功地做到了把时间复杂度压缩到O(log n),继续膜拜发明者。。
以下是代码,为了训练读者的代码阅读能力,本代码不添加注释(虽然是我懒)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct node{ int c, l; }; node da[40005]; int n, cnt; int has[40005], c[40005]; int get_num(); bool cmp(node a, node b) { return a.c<b.c; } inline int lowbit(int x) { return x&(-x); } inline int add(int x, int d) { while(x<=n) { c[x]+=d; x+=lowbit(x); } } inline int sum(int x) { int tmp=0; while(x>0) { tmp+=c[x]; x-=lowbit(x); } return tmp; } int main() { n=get_num(); for(int i=1;i<=n;i++) { da[i].c=get_num(); da[i].l=i; } sort(da+1,da+n+1,cmp); for(int i=1;i<=n;i++) { has[da[i].l]=i; } long long ans=0; for(int i=n;i>=1;i--) { add(has[i],1); ans+=sum(has[i]-1); } cout<<ans<<"\n"; return 0; } inline int get_num() { int ans=0; char tmp; tmp=getchar(); while(tmp>'9'||tmp<'0') tmp=getchar(); while(tmp<='9'&&tmp>='0') { ans=ans*10+tmp-48; tmp=getchar(); } return ans; } |