「vijos-bashu」序列杀手 / 「CodeChef FNCS」Chef and Churu - 分块套分块 | Bill Yang's Blog

「vijos-bashu」序列杀手 / 「CodeChef FNCS」Chef and Churu - 分块套分块

题目大意

传送门


题目分析

对$f$数组拆分成$\sqrt n$个块,每个块预处理这个块中每一个$a_i$出现了多少次,以及初始状态下每个块$f_i$的和,用差分可以在$O(n\sqrt n)$时间内完成预处理。

对于修改操作,直接将每一段的$f_i$的和更新一下,因为预处理了每个数的出现次数所以很方便实现,时间复杂度$O(\sqrt n)$。

对于询问操作,将询问区间分为整块和零散的点。
整块已经维护出和,故$O(\sqrt n)$即可完成整块的询问,剩下的$O(\sqrt n)$个单点可以使用树状数组求和,但时间复杂度是$O(\sqrt n \log n)$,本题可过。
我们可以对$a$数组再分块,对$a$中每个块作前缀和,修改的时候重构对应块的前缀和并重构块与块之间的前缀和,这样我们对于每个零碎的点就可以$O(1)$得到其值。
询问时间复杂度降为$O(\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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL 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=100005;
int n,m,Belong[maxn],l[maxn],r[maxn],Left[maxn],Right[maxn],BCC=0;
LL a[maxn],f[maxn],cnt[325][maxn],sum[maxn],sum_block[maxn];
void Modify(int pos,LL v) {
for(int i=1; i<=BCC; i++)f[i]+=(v-a[pos])*cnt[i][pos];
a[pos]=v;
for(int i=pos; i<=Right[Belong[pos]]; i++) {
if(i==Left[Belong[pos]])sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];
}
for(int i=Belong[pos]; i<=BCC; i++)sum_block[i]=sum_block[i-1]+sum[Right[i]];
}
LL Sum(int x,int y) {
int L=Belong[x],R=Belong[y];
LL ans=0;
if(L==R) {
if(x==Left[L])return sum[y];
else return sum[y]-sum[x-1];
} else if(L+1==R) {
if(x==Left[L])return sum[Right[L]]+sum[y];
else return sum[Right[L]]-sum[x-1]+sum[y];
} else {
if(x==Left[L])return sum_block[R-1]-sum_block[L-1]+sum[y];
else return sum[Right[L]]-sum[x-1]+sum_block[R-1]-sum_block[L]+sum[y];
}
}
LL Query(int x,int y) {
int L=Belong[x],R=Belong[y];
LL ans=0;
if(L==R)for(int i=x; i<=y; i++)ans+=Sum(l[i],r[i]);
else {
for(int i=L+1; i<=R-1; i++)ans+=f[i];
for(int i=x; i<=Right[L]; i++)ans+=Sum(l[i],r[i]);
for(int i=Left[R]; i<=y; i++)ans+=Sum(l[i],r[i]);
}
return ans;
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++) {
l[i]=Get_Int();
r[i]=Get_Int();
}
int size=sqrt(n);
for(int i=1; i<=n; i++) {
Belong[i]=(i-1)/size+1;
if(!Left[Belong[i]])Left[Belong[i]]=i,BCC++;
Right[Belong[i]]=i;
if(i==Left[Belong[i]])sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];
}
for(int i=1; i<=BCC; i++) {
for(int j=Left[i]; j<=Right[i]; j++) { //差分
cnt[i][l[j]]++;
cnt[i][r[j]+1]--;
}
for(int j=1; j<=n; j++) { //统计
cnt[i][j]+=cnt[i][j-1];
f[i]+=cnt[i][j]*a[j];
}
}
for(int i=1; i<=BCC; i++)sum_block[i]=sum_block[i-1]+sum[Right[i]];
m=Get_Int();
for(int i=1; i<=m; i++) {
int opt=Get_Int(),x=Get_Int();
LL y=Get_Int();
if(opt==1)Modify(x,y);
else printf("%lld\n",Query(x,y));
}
return 0;
}
0%