以前一般用树状数组和线段树做这种题 这次换个思路试试，归并排序！ #include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];L

题意：一个数列，给出一些区间，计算这个区间有多少子区间逆序对数为k。 分析：直接计算k不好算，把问题转化为<=k的子区间数减去<k的子区间数。首先由两个指针可以求出每一个点的满足<=k或<k的最右边界。得到r1和r2数组。    最后所求即为sum(min(r1i,r)-l+1) (i>=l&&i<=r)，r数组单调递增，二分即可。 #include<iostream>#include

This way 题意： 给你一个数组a，设r为a的某种排序， t ( r ) t(r) t(r)为r中逆序对的个数，问你 ∑ b t ( r ) \sum{b^{t(r)}} ∑bt(r)是多少 题解： 值不重复的时候，我们考虑第i大的数，它和前面i-1个数组成的逆序对的所有可能是0-（i-1） 那么答案就乘上 ( 1 + b + b 2 + . . . + b i − 1 ) (1+b

Divide and Conquer The attached le Q8.txt contains 100,000 integers between 1 and 100,000 (each row has a single integer), the order of these integers is random and no integer is repeated. 刚写程序是用的

1、http://blog.csdn.net/sdjzping/article/details/20381665 2、题目大意: 有n个数字，定义i<j并且a[i]>a[j]这样的一对数为逆序对，求这个数中有多少逆序对， 3、题目分析 看着题目很简单，但是n=65537,两重for循环找必超时，所以想到了用树状数组，但是交了好几遍都错了，runtime error,原因就是数组中的数字可以

欢迎访问我的pat顶级题解目录哦 题目描述 算法设计 可以利用树状数组来解决这个问题。 由于输入序列的每个元素的值都不会超过 1 0 5 10^5 105，因此我们可以开辟一个长 1 0 5 + 5 10^5+5 105+5的树状数组c。设计getSum(x)函数表示1到x这些数字在序列中出现次数之和。设计update函数用于更新数字出现次数。 我们要对整个序列A进行两次遍历，第一次从前

欢迎访问我的pat顶级题解目录哦 题目描述 算法设计 可以利用树状数组来解决这个问题。 由于n不会超过 1 0 3 10^3 103 ，因此我们可以开辟一个长1005的树状数组c。设计getSum(x)函数表示1到x这些数字在序列中出现次数之和。设计update函数用于更新数字出现次数。 首先我们要明白如果我们定义A[i]左侧比A[i]大的数字个数为S[i]，那么对于序列A[i]~A[j