「bzoj3787」Gty的文艺妹子序列 - 分块+树状数组+重构 | Bill Yang's Blog
0%

「bzoj3787」Gty的文艺妹子序列 - 分块+树状数组+重构

题目大意

    给定一个正整数序列$a(1\le a_i\le n)$,支持单点修改,对于每次询问,输出$a_l\ldots a_r$中的逆序对数,强制在线。


题目分析

上题一样,我们可以分块+树状数组预处理。

若此时我们再维护主席树的话,就要套一个树状数组,时间复杂度$O(n\sqrt n\log^2 n)\approx O(n^2)$,不能接受,故考虑使用上题的另一种思路。

每次我们更新点$a_i$时,要对对应的块信息进行维护,需要维护所有$R\ge Belong[i],L\le Belong[i]$的$f[L,R]$和$small,big$的前缀和,时间复杂度无法接受,似乎陷入僵局。

不妨修改状态定义,设$f[L,R]$表示仅计算$L$和$R$块产生的逆序对(不包括$L,R$本身产生的逆序对,$f[i,i]$无意义),$g[B,v]$表示前$B$个块,值为$v$的个数,$ans[B]$表示第$B$个块产生的逆序对数。

那么整块妹子$[L+1,R-1]$产生的答案就是:

前缀和优化后得到:

而$small,big$均可以表示为$g$的前缀和。

对$f[L,R]$的修改,枚举$L$,利用$g[]$修改掉对左边的影响,对右边的同理。

那么我们需要一个支持单点修改求前缀和的数据结构,它就是:树状数组!

用struct封装一下写起来可读性更高。


代码

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
#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],Ans[maxb],Belong[maxn],Left[maxb],Right[maxb],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;

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


struct BIT3 {
int c[maxb];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=BCC; i+=lowbit(i))c[i]+=v;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} f[maxb];

void change(int pos,int v) {
int block=Belong[pos];
for(int i=block+1; i<=BCC; i++) {
int tmp=-(num[i].sum(a[pos]-1)-num[i-1].sum(a[pos]-1));
tmp+=num[i].sum(v-1)-num[i-1].sum(v-1);
f[block].add(i,tmp);
}
for(int i=1; i<block; i++) {
int tmp=-((num[i].sum(n)-num[i].sum(a[pos]))-(num[i-1].sum(n)-num[i-1].sum(a[pos])));
tmp+=(num[i].sum(n)-num[i].sum(v))-(num[i-1].sum(n)-num[i-1].sum(v));
f[i].add(block,tmp);
}
for(int i=block; i<=BCC; i++) {
num[i].add(a[pos],-1);
num[i].add(v,1);
}
a[pos]=v;
Ans[block]=0;
for(int i=Left[block]; i<=Right[block]; i++) {
Ans[block]+=bit.sum(a[i]+1);
bit.add(a[i],1);
}
for(int i=Left[block]; i<=Right[block]; i++)bit.clear(a[i]);
}

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(a[i]+1);
bit.add(a[i],1);
}
for(int i=left; i<=right; i++)bit.clear(a[i]);
return ans;
}
for(int i=L+1; i<=R-1; i++)ans+=Ans[i]+f[i].sum(R-1);
for(int i=left; i<=Right[L]; i++) {
ans+=num[R-1].sum(a[i]-1)-num[L].sum(a[i]-1);
ans+=bit.sum(a[i]+1);
bit.add(a[i],1);
}
for(int i=Left[R]; i<=right; i++) {
ans+=num[R-1].sum(n)-num[R-1].sum(a[i])-(num[L].sum(n)-num[L].sum(a[i]));
ans+=bit.sum(a[i]+1);
bit.add(a[i],1);
}
for(int i=left; i<=Right[L]; i++)bit.clear(a[i]);
for(int i=Left[R]; i<=right; i++)bit.clear(a[i]);
return ans;
}

int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
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++) {
num[i]=num[i-1];
for(int j=Left[i]; j<=Right[i]; j++)num[i].add(a[j],1);
}
for(int i=1; i<=BCC; i++) {
for(int k=Left[i]; k<=Right[i]; k++) {
Ans[i]+=bit.sum(a[k]+1);
bit.add(a[k],1);
}
for(int j=i+1; j<=BCC; j++)
for(int k=Left[j]; k<=Right[j]; k++)
f[i].add(j,bit.sum(a[k]+1));
for(int k=Left[i]; k<=Right[i]; k++)bit.clear(a[k]);
}
q=Get_Int();
for(int i=1; i<=q; i++) {
int opt=Get_Int(),left=Get_Int()^lastans,right=Get_Int()^lastans;
if(opt==0)lastans=query(left,right),printf("%d\n",lastans);
else change(left,right);
}
return 0;
}
姥爷们赏瓶冰阔落吧~