xjtoj-14-wmq的队伍-k元逆序对

题目链接

题意：给出一个序列（n<=2*10e4），问这个序列中存在多少组k(k<=100)元逆序对，将答案对1e9+7取模

思路：西交出的北方高校训练题……这个题出真的很好呀……李主席真的好强好强呀……我们可以考虑以前求过的二元逆序对，利用线段树或者树状数组来求解。当我们已知以某个位置的数位结尾时的二元逆序对个数时，我们是不是也能用同样的方法来求三元逆序对个数？当求完k-1元逆序对个数时，将树状数组清空，再根据排列从左到右，将每个数x为结尾的k-1元逆序对个数插入在这个点，那么当我们在后面插入某个比这个x小的数时，我们可以在log时间内求和出所有结尾比这个数大的所有k-1元逆序对个数，这就是以这个更小的数为结尾的k元逆序对个数。

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
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
long long mod=1e9+7;
long long tree[300005];
long long last[300005];
long long now[300005];
int a[300005];
int lowbit(int x)
{
	return x&-x;
}
int n;
void add(int k,int num)
{
	while(k<=n)
	{
		tree[k]=(tree[k]+num)%mod;
		k+=lowbit(k);
	}
}
long long get(int k)
{
	long long sum=0;
	while(k>0)
	{
		sum=(sum+tree[k])%mod;
		k-=lowbit(k);
	}
	return  sum;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int k;
		scanf("%d%d",&n,&k);
		memset(tree,0,sizeof(tree));
		memset(last,0,sizeof(last));
		memset(now,0,sizeof(now));
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)last[i]=1;  // 1元逆序对，个数都为1 
		for(int m=2;m<=k;m++)
		{
			memset(tree,0,sizeof(tree));
			for(int i=1;i<=n;i++)
			{
				now[i]=(get(n)-get(a[i])+mod)%mod;
				add(a[i],last[i]);	 
			}
			for(int i=1;i<=n;i++)last[i]=now[i];
		}
		long long ans=0;
		for(int i=1;i<=n;i++)ans=(ans+last[i])%mod;
		printf("%lld\n",ans);
	}
	return 0;
 }