题意
求一列数字的逆序数。
思路
由于数字很大,所以不能直接求,这里先对原数列排序之后,求出原下标的逆序数即可
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define lowbit(x) (x&(-x)) using namespace std; const int nMax = 500010; typedef long long ll; struct rrr{ ll a,b; }num[nMax]; bool cmp(rrr a, rrr b){ if(a.a<b.a)return 1; return 0; } int n, arr[nMax]; void add(int loc, int val){ while(loc <= n){ arr[loc] += val; loc += lowbit(loc); } } int sum(int loc){ int res = 0; while(loc >= 1){ res += arr[loc]; loc -= lowbit(loc); } return res; } int main(){ int i; while(scanf("%d",&n)!=EOF&&n){ for(i = 1; i <= n; i ++){ scanf("%I64d",&num[i].a); num[i].b = i; } sort(num + 1, num + n + 1 ,cmp); memset(arr, 0,sizeof(arr)); ll res = 0; for(i = 1; i <= n; i++){ res += num[i].b - 1 - sum(num[i].b); // cout<<num[i].b<<" "<<sum(num[i].b)<<endl; add(num[i].b, 1); } printf("%I64d\n",res); } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1744555
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
线段树、树状数组算法入门 加 poj解题报告 pdf文档
关于二部图、线段数、树状数组、树的分治的一些POJ题目的解答
7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小...
自己总结的一些算法代码模板,有基本的排序算法、图最短路径算法,也有树状数组、线段树这些骚操作. /nowcoder/coding-interviews/ 牛客网上《剑指offer》编程题C++代码,比该书的参考代码要简明许多,更加OJ风格. /...
1.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.1 DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.2 DC3 . . . ...