This is not the end.

0%

BZOJ3744 Gty的妹子序列

Posted on

Sol

参考了zzq的blog

考虑分块。对于一次询问，涉及到的元素有如下的形式：

讨论逆序对中的两个元素分别属于哪个部分，即得到一个时间复杂度 $O(n\sqrt n)$ ，空间复杂度 $O(n\sqrt n)$ 的算法：

$x\in A,y\in A$

预处理每个块的每个后缀中的逆序对数。

$x\in C,y\in C$

预处理每个块的每个后缀中的逆序对数。

$x\in B,y\in B$

预处理出 $f_{i,j}$ 表示第 $i$ 块到第 $j$ 块这个区间中的元素两两之间的逆序对数。

具体地，先对每个块预处理出块内的元素排序后的结果，然后归并求出 $g_{i,j}$ 表示第 $i$ 块和第 $j$ 块中的元素两两之间的逆序对数。这一步的复杂度是 $O(n\log n + \sqrt n \cdot (\sqrt n)^2 ) = O(n\sqrt n)$ 。

然后对 $g_{i,j}$ 做个类似区间 dp 的东西就能得到 $f$ （即：$f_{i,j} = g_{i,j} + f_{i,j-1} + f_{i+1,j} - f_{i+1,j-1}$）。这一步的复杂度是 $O((\sqrt n)^2) = O(n)$ 。

$x\in A,y\in B$

预处理出 $s_{i,j}$ 表示前 $i$ 块中小于等于 $j$ 的数有多少个，然后枚举 $A$ 中的每一个数进行查询就好。预处理复杂度 $O(n\sqrt n)$ ，单次查询的复杂度 $O(\sqrt n)$ 。空间复杂度是 $O(n\sqrt n)$ 。

$x\in B,y\in C$

同 $x\in A, y\in B$ 。

$x\in A,y\in C$

对 $A$ 所在的整块和 $C$ 所在的整块进行归并，复杂度 $O(\sqrt n)$ 。

具体地，归并的时候每加入一个 $C$ 中的元素，就让 cnt++ ；每加入一个 $A$ 中的元素，就让 ans+=cnt 。

Code

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=5e4+10,M=260;
int a[N],b[N],n,m;

namespace BIT {
	int a[N];
	void I(int i,int t) { for(;i<=m;i+=i&-i) a[i]+=t; }
	int Q(int i) { int ans=0; for(;i;i-=i&-i) ans+=a[i]; return ans; }
}

int bel[N],T;
int pos[N],s[M][N];
int f[M][M],pre[N],suf[N];
bool cmppos(int x,int y) { return a[x]==a[y]?x<y:a[x]<a[y]; }
int Qry(int x,int lv,int rv) { return s[x][rv]-s[x][lv-1]; }
int Qry(int l,int r,int lv,int rv) { return Qry(r,lv,rv)-Qry(l-1,lv,rv); }

int ql,qr,lastans;

int main() {
	rd(n);
	for(int i=1;i<=n;++i) rd(a[i]),b[i]=a[i];
	sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	
	T=ceil(sqrt(n));
	for(int i=1;i<=n;++i) bel[i]=(i-1)/T+1,pos[i]=i;
	for(int i=1;i<=n;i+=T) {
		int len=min(T,n-i+1);
		sort(pos+i,pos+i+len,cmppos);
		
		for(int j=1;j<=m;++j) s[bel[i]][j]=s[bel[i]-1][j];
		for(int j=i;j<i+len;++j) s[bel[i]][a[j]]++;
		
		for(int j=i;j<i+len;++j) pre[j]=BIT::Q(m-(a[j]+1)+1),BIT::I(m-a[j]+1,1);
		for(int j=i;j<i+len;++j) BIT::I(m-a[j]+1,-1);
		for(int j=i+len-1;j>=i;--j) suf[j]=BIT::Q(a[j]-1),BIT::I(a[j],1);
		for(int j=i+len-1;j>=i;--j) BIT::I(a[j],-1);
		for(int j=i+1;j<i+len;++j) pre[j]+=pre[j-1];
		for(int j=i+len-2;j>=i;--j) suf[j]+=suf[j+1];
	}
	for(int i=1;i<=bel[n];++i) for(int j=1;j<=m;++j) s[i][j]+=s[i][j-1];

	for(int i=1;i<=bel[n];++i) f[i][i]=suf[(i-1)*T+1];
	for(int i=1;i+1<=bel[n];++i) f[i][i+1]=suf[(i-1)*T+1]+suf[i*T+1];
	for(int l=1;l<=bel[n];++l)
		for(int r=l+1;r<=bel[n];++r) {
			int cnt=0;
			int pl=(l-1)*T+1,liml=l*T;
			int pr=(r-1)*T+1,limr=min(r*T,n);
			while(pl<=liml||pr<=limr)
				if(pl<=liml&&(pr>limr||a[pos[pl]]<=a[pos[pr]]))
					f[l][r]+=cnt,pl++;
				else cnt++,pr++;
		}
	for(int len=3;len<=bel[n];++len)
		for(int l=1;l+len-1<=bel[n];++l) {
			int r=l+len-1;
			f[l][r]+=f[l+1][r]+f[l][r-1]-f[l+1][r-1];
		}
		
	int q; rd(q);
	while(q--) {
		rd(ql),rd(qr);
		ql^=lastans,qr^=lastans;
		if(ql>qr) swap(ql,qr);
		if(bel[ql]==bel[qr]) {
			int pl=(bel[ql]-1)*T+1,pr=min(bel[ql]*T,n);
			if(ql==pl) lastans=pre[qr];
			else if(qr==pr) lastans=suf[ql];
			else {
				lastans=pre[qr]-pre[ql-1];
				int cnt=0;
				for(int i=pl;i<=pr;++i) {
					if(pos[i]>=ql&&pos[i]<=qr) cnt++;
					if(pos[i]<=ql-1) lastans-=cnt;
				}
			}
		}
		else {
			int bl=bel[ql]+1,br=bel[qr]-1;
			if(ql==(bel[ql]-1)*T+1) bl--;
			if(qr==min(bel[qr]*T,n)) br++;
			lastans=f[bl][br]+(bel[ql]==bl?0:suf[ql])+(bel[qr]==br?0:pre[qr]);
			for(int i=ql;bel[i]!=bl;++i) lastans+=Qry(bl,br,1,a[i]-1);
			for(int i=qr;bel[i]!=br;--i) lastans+=Qry(bl,br,a[i]+1,m);
			if(bel[ql]!=bl&&bel[qr]!=br) {
				int cnt=0;
				int pl=(bl-2)*T+1,liml=(bl-1)*T;
				int pr=br*T+1,limr=min((br+1)*T,n);
				while(pl<=liml||pr<=limr)
					if(pl<=liml&&(pr>limr||a[pos[pl]]<=a[pos[pr]])) {
						if(pos[pl]>=ql) lastans+=cnt;
						pl++;
					}
					else {
						if(pos[pr]<=qr) cnt++;
						pr++;
					}
			}
		}
		printf("%d\n",lastans);
	}
	return 0;
}