Time Limit: 10 second
Memory Limit: 2 MB
问题描述
给定一个序列a1,a2...an。如果存在i小于j 并且ai大于aj，那么我们称之为逆序对，求给定序列中逆序对的数目
Input
第一行为n，表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
Output
所有逆序对的总数
Sample Input
4
3
2
3
2
Sample Output
3
【题解】
n的最大值为10W。
如果用线段树来解的话，求解的思路都相同。
我就直接复制前一篇的例子了。
比如
3 2 8 5
将它们排序(从大到小)
8 5 3 2
先把8放进去(原来的位置是3)
但是在放之前，先检查位置3之前有没有其他数字放进去了(如果放进去了肯定是比8大的数字，但是它们的下标又小于3(逆序对！));
因为没有
所以就把下标3对应的位置改为1；
即0 0 1 0
然后是第大的5(原来的位置是4)
则看看4前面有多少个元素已经放进去了(前缀和！)。
发现有1个。则答案递增1；
然后把arr[4] 改为1
即0 0 1 1
然后是第三大的数字3，它原来的位置是1,但是1前面没有数字已经放进去。则不递增答案。
最后是最小的元素2，它原来的位置就是2，然后位置2之前有一个数字3已经放在了位置1.即下标1的前缀和为1.则答案递增1.
最后答案为2；
这里实际上就是涉及到单节点的递增问题。
只要在改动的时候往上更新节点就可以了。很简单的线段树模型。
然后前缀和的话就是返回(1,pos)的和,线段树记录的是区间和的。
但是要注意一个问题。就是出现相同数字的情况。
则我们在写比较函数的时候，让相同的数字，之前的位置大的放在后面。然后我们处理到连续的相同数字的时候。就记录这是连续相同数字里面的第i个。
在累加完前缀和之后答案减去i-1，因为相同大小就不算逆序对了;
【代码】
#include <cstdio>
#include <algorithm> struct data2
{
int d, pos;
}; __int64 sum[400001] = { 0 },ans = 0; //线段树的数组貌似不用开4倍。。感觉2.2倍就够了。。
int n;
data2 a[100001];//以结构体的形式写，比较好写比较函数。 __int64 query(int l, int r, int begin, int end, int rt)//询问区间(l,r)，当前节点的区间为(begin,end),当前节点为rt.
{
if (l > r)//如果询问的区间不合规则就退出
return 0;
if (l <= begin && end <= r) //如果这个节点所代表的区间在所要求的区间内，则返回这个区间的和。
{
return sum[rt];
}
int m = (begin + end) / 2;//获取这个节点所代表的区间的中点
__int64 re = 0;
if (l <= m)//如果左半部分有一部分区间在这个节点的左半部分则加上那一部分(当然会一直缩小区间直到找到那块区间为止)
re += query(l, r, begin, m, rt <<1);
if (m < r) //如果这个节点的区间的右半部分有一部分和所求区间有交集，则加上右半部分那段有交集的区间的和。
re += query(l, r, m+1, end, rt<<1|1);
return re;
} int cmp(const data2 &a, const data2 &b)//比较函数。
{
if (a.d > b.d)//第一关键是数字从大到小排序。
return 1;
if (a.d == b.d && a.pos < b.pos)//然后是如果数字相同则之前的位置大的在后面。
return 1;
return 0;
} void updata(int p, int num, int begin, int end, int rt)//要让数组下标为p的节点递增num,然后当前的节点所代表的区间为[begin,end],当前节点为rt
{//这里的p可以换成是区间理解为[p,p]
if (begin == end)//如果找到了这个节点p
{
sum[rt] += num;//在这个节点的和累加num
return;
}
int m = (begin + end) / 2;//取得这个节点所代表的区间中点
if (p <= m)//如果这个下标在中点的左边就往左递归节点
updata(p, num, begin, m, rt<<1);
else//否则往右递归节点
updata(p, num, m+1, end, rt<<1|1);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];//因为子节点可能发生了改变，所以要更新当前节点的区间和。
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
//freopen("F:\\rush_out.txt", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].d);
a[i].pos = i; //记录原先的位置
}
std::sort(a + 1, a + 1 + n, cmp);//进行从大到小排序
int now = 0;
for (int i = 1; i <= n; i++)//假设当前是连续相同的数字中第x个,则now始终等于x-1
{
if (i != 1 && a[i - 1].d == a[i].d)
now++;
else
now = 0;
ans += query(1, a[i].pos - 1, 1, n, 1);
ans -= now;//因为会重复累加相同的数字，所以要减掉那几个相同的。
updata(a[i].pos, 1, 1, n, 1);//把a[i].pos递增1，然后要修改与之相关的区间的和。
}
printf("%I64d", ans);
return 0;
}