crazy_cloud's Blog
0%

在线解决区间逆序对个数统计问题的 $O(n\sqrt n)$ 算法

Posted on Edited on In

简介

本文将介绍一种 \(O(n\sqrt n)\) 解决区间逆序对计数的在线算法。

似乎又是某分块中学那边的奇技淫巧

我会分块！

考虑将序列分块。然后分以下几种情况讨论：

两个不相交序列互相之间的逆序对统计

标题指的是给你两个序列，一个在前面，一个在后面，然后求后面序列的元素在前面序列中的逆序对个数。

后面我们会多次遇到这个问题，因此先讲这个。

直接归并排序统计即可做到线性。

为了降低时间复杂度我们要对每一块预排序记录排名，这样我们就可以省去每次的排序。

定义 \([x,y]\times[a,b]\) 表示对区间 \([x,y]\)和\([a,b]\) 执行此操作。

块内的区间逆序对统计

解决完全被某一块包含的询问，令 \(g_i\) 表示第 \(i\) 个元素一直到其所在块开头形成的区间内的逆序对个数。

那么假设我们询问的是 \([\mathrm{st},\mathrm{en}]\) 这个区间，它被块 \([l,r]\) 完全包含，显然答案是 \(g_{\mathrm{en}}-g_{\mathrm{st}-1}-[l,\mathrm{st}-1]\times[\mathrm{st},\mathrm{en}]\)

\(g\) 函数可以使用离散化+树状数组在开始时预处理出来。

块间的逆序对统计

设 \(f_{i,j}\) 表示从第 \(i\) 块一直到第 \(j\) 块形成的区间的逆序对个数。

令 \(\mathrm{st}_i,\mathrm{en}_i\) 分别表示第 \(i\) 块的开始和结束位置。

显然我们有 \(f_{i,j}=f_{i,j-1}+f_{i+1,j}-f_{i+1,j-1}+[\mathrm{st}_i,\mathrm{en}_i]\times[{st}_j,{en}_j]\)。

于是就可以 \(O(n\sqrt n)\) 计算出来。

散块与散块

直接当不相交序列归并即可。

散块与整块

令 \(h_{i,j}\) 表示第 \(i\) 个元素对第 \(j\) 块的贡献。这个怎么处理呢？

将所有元素排序依次插入，记录每一块已有的元素，就能算出 \(h\) 了。

因为散块一定是一个整块的前缀和后缀，我们再对 \(h_{i,j}\) 的 \(i\) 做前缀和就能快速查询散块对一个整块的贡献了。

最后总的时间复杂度就是 \(O(n\sqrt n)\) 的了。

代码实现

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int buf[30];

inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	for (;x;x/=10) buf[++buf[0]]=x%10;
	if (!buf[0]) buf[++buf[0]]=0;
	for (;buf[0];putchar('0'+buf[buf[0]--]));
}

const int N=50005;
const int B=250;

int a[N],g[N],bid[N],kth[N];
int st[B],en[B],tot[B];
int tmp[2][B];
int h[N][B];
int f[B][B];
int n,q,cnt,block_num,block_size,lastans;
bool is_online=0;

struct data
{
	int key,id;

	inline data(int key_=0,int id_=0){key=key_,id=id_;}

	inline bool operator<(data const d)const{return key<d.key;}
}srt[N];

inline int lowbit(int x){return x&-x;}

struct Fenwick_tree
{
	int v[N];

	inline void modify(int x,int delta){for (;x<=n;x+=lowbit(x)) v[x]+=delta;}

	inline int query(int x)
	{
		int ret=0;
		for (;x;x-=lowbit(x)) ret+=v[x];
		return ret;
	}
}t;

void discretize()
{
	for (int i=1;i<=n;++i) srt[i]=data(a[i],i);
	sort(srt+1,srt+1+n),cnt=0;
	for (int i=1;i<=n;++i) a[srt[i].id]=cnt+=srt[i].key!=srt[i-1].key;
}

inline int merge()
{
	int cur1=1,cur2=1,ret=0;
	for (;cur1<=tmp[0][0]||cur2<=tmp[1][0];)
		if (cur2>tmp[1][0]||cur1<=tmp[0][0]&&tmp[0][cur1]<=tmp[1][cur2]) ++cur1;
		else ret+=tmp[0][0]-cur1+1,++cur2;
	return ret;
}

inline bool cmp(int x,int y){return a[x]<a[y];}

void process()
{
	//divide the sequence into several blocks
	block_size=(int)trunc(sqrt(n));
	for (int st_=1,en_;st_<=n;st_=en_+1)
	{
		en_=min(n,st_+block_size-1),st[++block_num]=st_,en[block_num]=en_;
		for (int i=st_;i<=en_;++i) bid[i]=block_num,kth[i]=i;
		sort(kth+st_,kth+en_+1,cmp);
	}
	//calculate g function
	for (int i=1;i<=block_num;++i)
	{
		memset(t.v,0,sizeof t.v);
		for (int j=st[i],cur=0;j<=en[i];++j) g[j]=cur+=t.query(cnt-a[j]),t.modify(cnt-a[j]+1,1);
	}
	//calculate f function
	for (int i=1;i<=block_num;++i) f[i][i]=g[en[i]];
	for (int l=2;l<=block_num;++l)
		for (int i=1,j;i+l-1<=block_num;++i)
		{
			j=i+l-1,f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
			tmp[0][0]=tmp[1][0]=0;
			for (int k=st[i];k<=en[i];++k) tmp[0][++tmp[0][0]]=a[kth[k]];
			for (int k=st[j];k<=en[j];++k) tmp[1][++tmp[1][0]]=a[kth[k]];
			f[i][j]+=merge();
		}
	//calculate h function
	for (int lcur=1,rcur;lcur<=n;)
	{
		for (rcur=lcur;rcur<=n&&srt[lcur].key==srt[rcur].key;++rcur)
			for (int i=bid[srt[rcur].id]+1;i<=block_num;++i) h[srt[rcur].id][i]=tot[i];
		for (;lcur<rcur;++lcur) ++tot[bid[srt[lcur].id]];
	}
	for (int i=1;i<=block_num;++i) tot[i]=0;
	for (int lcur=n,rcur;lcur>=1;)
	{
		for (rcur=lcur;rcur>=1&&srt[lcur].key==srt[rcur].key;--rcur)
			for (int i=1;i<bid[srt[rcur].id];++i) h[srt[rcur].id][i]=tot[i];
		for (;lcur>rcur;--lcur) ++tot[bid[srt[lcur].id]];
	}
	for (int i=1;i<=block_num;++i)
		for (int j=st[i]+1;j<=en[i];++j)
			for (int k=1;k<=block_num;++k)
				h[j][k]+=h[j-1][k];
}

inline int query(int l,int st,int en,int r)
{
	int ret=(en==l-1?0:g[en])-(st==l?0:g[st-1]);
	tmp[0][0]=tmp[1][0]=0;
	for (int i=l;i<=r;++i) if (l<=kth[i]&&kth[i]<st) tmp[0][++tmp[0][0]]=a[kth[i]];
	for (int i=l;i<=r;++i) if (st<=kth[i]&&kth[i]<=en) tmp[1][++tmp[1][0]]=a[kth[i]];
	ret-=merge();
	return ret;
}

int main()
{
	freopen("girlseq.in","r",stdin),freopen("girlseq.out","w",stdout);
	n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	discretize(),process(),q=read(),lastans=0;
	for (int l,r,lid,rid;q--;)
	{
		lid=bid[l=read()^(lastans*is_online)],rid=bid[r=read()^(lastans*is_online)];
		if (l!=st[lid]) ++lid;
		if (r!=en[rid]) --rid;
		if (bid[l]==bid[r]) lastans=query(st[bid[l]],l,r,en[bid[l]]);
		else
		{
			lastans=query(st[bid[l]],l,st[lid]-1,en[bid[l]])+query(st[bid[r]],en[rid]+1,r,en[bid[r]])+f[lid][rid];
			tmp[0][0]=tmp[1][0]=0;
			for (int i=st[bid[l]];i<=en[bid[l]];++i) if (l<=kth[i]&&kth[i]<st[lid]) tmp[0][++tmp[0][0]]=a[kth[i]];
			for (int i=st[bid[r]];i<=en[bid[r]];++i) if (en[rid]<kth[i]&&kth[i]<=r) tmp[1][++tmp[1][0]]=a[kth[i]];
			lastans+=merge();
			for (int i=lid;i<=rid;++i) lastans+=h[st[lid]-1][i]-h[l-1][i]+(en[bid[r]]!=r)*h[r][i];
		}
		write(lastans),putchar('\n');
	}
	fclose(stdin),fclose(stdout);
	return 0;
}