题型二:逆序对的扩展

在完成了分配任务之后,西部 314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(),他们分别用 V 和  的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 nn 个点,经测量发现这 nn 个点的水平位置和竖直位置是两两不同的。

西部 314314 认为这幅壁画所包含的信息与这 nn 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),,(n,yn)(1,y1),(2,y2),…,(n,yn),其中 y1yny1∼yn 是 11 到 nn 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1i<j<kn1≤i<j<k≤n 且 yi>yjyj<ykyi>yj,yj<yk,则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1i<j<kn1≤i<j<k≤n 且 yi<yjyj>ykyi<yj,yj>yk,则称这三个点构成  图腾;

西部 314 想知道,这nn个点中两个部落图腾的数目。

因此,你需要编写一个程序来求出 V 的个数和  的个数。

输入格式

第一行一个数 nn

第二行是 nn个数,分别代表 y1y2,,yny1,y2,…,yn

输出格式

两个数,中间用空格隔开,依次为 V 的个数和  的个数。

数据范围

对于所有数据,n200000n≤200000,且输出答案不会超过 int64。
y1yny1∼yn是 11到 nn 的一个排列。

样例输入

1
2
5
1 5 3 2 4

输出样例:

1
3 4

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
int a[N], tr[N];
int f[N];
int g[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL ask(int x)
{
LL res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++)
{
int y = a[i];
f[i] = ask(y - 1);
g[i] = ask(n) - ask(y);
add(y, 1);
}
memset(tr, 0, sizeof tr);
LL resV = 0, resA = 0;
for(int i = n; i; i --)
{
int y = a[i];
resV += (LL)g[i] * (ask(n) - ask(y));
resA += (LL)f[i] * ask(y - 1);
add(y, 1);
}
cout << resV << " " << resA << endl;
return 0;
}

1、求所以V 的个数和  的个数,而且严格y1yny1∼yn是 11到 nn 的一个排列,所以可以不用离散化处理,求vv的个数,所以求出每一个数,左边比它的大的和右边都比它大,然后相乘在全部相加既可,求 的个数也是如此的思路

2、从左到右扫描一遍,f[i]f[i]存储的是当前比a[i]a[i]小的集合,g[i]g[i]存储的是当前比a[i]a[i]大的集合,然后建树

3、重新初始化,然后从从右到左扫描一遍

4、树状数组求逆序对,让我们知道了如何在一个序列中计算每个数后面有多少个数比它小,因此我们可以通过这个性质来做一些事情
‘v’图腾求法
倒序扫描序列aa,利用树状数组求出每个a[i]a[i]后面有几个数比它大记录为g[i]g[i]
正序扫描序列aa,利用树状数组求出每个a[i]a[i]前面有几个数比它大,记录为r[i]r[i]
’^’图腾求法
倒序扫描序列aa,利用树状数组求出每个a[i]a[i]后面有几个数比它小,记录为g[i]g[i]
正序扫描序列aa,利用树状数组求出每个a[i]a[i]前面有几个数比它小,记录为f[i]f[i]

转载自这里