「bzoj3744」Gty的妹子序列 - 分块+树状数组(+主席树) | Bill Yang's Blog
0%

「bzoj3744」Gty的妹子序列 - 分块+树状数组(+主席树)

题目大意

    给定一个正整数序列$a$,对于每次询问,输出$a_l\ldots a_r$中的逆序对数,强制在线。


题目分析

逆序对数不好进行处理,一般离线处理,但因为强制在线,不妨考虑暴力算法:分块。

将区间分为$\sqrt n$个块,并统计出$f[L,R]$表示$[L,R]$块内的答案(树状数组),这样我们询问的时候只需要分为整块的(妹子)和零碎的(妹子)。


接下来,我们只需要统计左零碎妹子与右零碎妹子所产生的逆序对 与 零碎妹子与整块妹子产生的逆序对。

第一部分可以树状数组暴力统计,第二部分可以使用主席树(有点卡常)。

当然我们可以不用主席树,我们统计$small[B,v]$表示前$B$个块中比$v$小的个数,$big[B,v]$表示前$B$个块中比$v$大的个数,显然我们均可以使用$O(n\sqrt n)$的时间维护出$small$和$big$,然后我们就可以方便统计第二部分产生的逆序对了。

时间复杂度$O(n\sqrt n\log 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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=50005,maxb=255;

int n,q,BCC,a[maxn],b[maxn],Belong[maxn],Left[maxb],Right[maxb],f[maxb][maxb],small[maxb][maxn],big[maxb][maxn],lastans;

struct BIT {
int c[maxn];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i>=1; i-=lowbit(i))c[i]+=v;
}
void clear(int x) {
for(int i=x; i>=1; i-=lowbit(i))c[i]=0;
}
int sum(int x) {
int sum=0;
for(int i=x; i<=n; i+=lowbit(i))sum+=c[i];
return sum;
}
} bit;

int query(int left,int right) {
int L=Belong[left],R=Belong[right],ans=0;
if(R-L<=1) {
for(int i=left; i<=right; i++) {
ans+=bit.sum(b[i]+1);
bit.add(b[i],1);
}
for(int i=left; i<=right; i++)bit.clear(b[i]);
return ans;
}
ans=f[L+1][R-1];
for(int i=left; i<=Right[L]; i++) {
ans+=small[R-1][b[i]-1]-small[L][b[i]-1];
ans+=bit.sum(b[i]+1);
bit.add(b[i],1);
}
for(int i=Left[R]; i<=right; i++) {
ans+=big[R-1][b[i]+1]-big[L][b[i]+1];
ans+=bit.sum(b[i]+1);
bit.add(b[i],1);
}
for(int i=left; i<=Right[L]; i++)bit.clear(b[i]);
for(int i=Left[R]; i<=right; i++)bit.clear(b[i]);
return ans;
}

void Discretization() {
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++)b[i]=a[i]=Get_Int();
Discretization();
int size=sqrt(n);
for(int i=1; i<=n; i++) {
Belong[i]=(i-1)/size+1;
if(!Left[Belong[i]])BCC++,Left[Belong[i]]=i;
Right[Belong[i]]=i;
}
for(int i=1; i<=BCC; i++) {
memcpy(small[i],small[i-1],sizeof(small[i-1]));
memcpy(big[i],big[i-1],sizeof(big[i-1]));
for(int j=Left[i]; j<=Right[i]; j++)small[i][b[j]]++,big[i][b[j]]++;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=BCC; j++)
small[j][i]+=small[j][i-1];
for(int i=n; i>=1; i--)
for(int j=1; j<=BCC; j++)
big[j][i]+=big[j][i+1];
for(int i=1; i<=BCC; i++) {
for(int j=i; j<=BCC; j++) {
f[i][j]=f[i][j-1];
for(int k=Left[j]; k<=Right[j]; k++) {
f[i][j]+=bit.sum(b[k]+1);
bit.add(b[k],1);
}
}
memset(bit.c,0,sizeof(bit.c));
}
q=Get_Int();
for(int i=1; i<=q; i++) {
int left=Get_Int()^lastans,right=Get_Int()^lastans;
lastans=query(left,right);
printf("%d\n",lastans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~