隐藏
「vijos-bashu」平面图杀手 / 「CodeChef QCHEF」Chef and Problems - 分块套Dp | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「vijos-bashu」平面图杀手 / 「CodeChef QCHEF」Chef and Problems - 分块套Dp

题目大意

传送门


题目分析

本题的平面图是没用的,根据题目信息,我们发现该平面图完全等价于一个序列(将第二维看做值)。

将序列分为$O(\sqrt n)$个块,用一次$O(\sqrt n\times\sqrt n)$的扫描求出每个块中每个元素出现的最早和最晚位置。
记$cal(x,y)$表示$i$在$x$块,$j$在$y$块所形成的答案。
因为每个块只可能有$O(\sqrt n)$种值,因此我们可以用$O(\sqrt n^3)$求出$cal(x,y)$。
对于块与块之间的答案我们可以利用区间Dp求出:

转移的时间复杂度是$O(\sqrt n^2)$的。

对于询问,拆成整块的和零散的点,整块答案可以直接得出,两端零散的点重建成块,用$O(\sqrt n)$的时间维护块内信息,用三次$O(\sqrt n)$的扫描得出答案。

这样写的常数较大,理论时空复杂度均为$O(n\sqrt n)$,但实际效率较低,可以直接分块+链表二分,虽然复杂度增加$\log$,但常数很小,实际效率很高。


代码

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
#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=100005,maxb=sqrt(maxn)+5;
int n,m,k,a[maxn],Belong[maxn],Left[maxn],Right[maxn],BCC=0,First[maxb][maxn],Last[maxb][maxn],cal[maxb][maxb],f[maxb][maxb],LMax[maxb][maxn],RMax[maxb][maxn];
vector<int>exist[maxb];
void build(int cnt,int L,int R) {
for(int i=0; i<exist[cnt].size(); i++)First[cnt][exist[cnt][i]]=0x3f3f3f3f,Last[cnt][exist[cnt][i]]=0;
exist[cnt].clear();
for(int i=L; i<=R; i++) {
if(First[cnt][a[i]]==0x3f3f3f3f) {
First[cnt][a[i]]=i;
exist[cnt].push_back(a[i]);
}
Last[cnt][a[i]]=i;
}
}
int main() {
n=Get_Int();
m=Get_Int();
k=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]])Left[Belong[i]]=i,BCC++;
Right[Belong[i]]=i;
}
memset(First,0x3f,sizeof(First));
for(int i=1; i<=BCC; i++)
for(int j=Left[i]; j<=Right[i]; j++) {
if(First[i][a[j]]==0x3f3f3f3f) {
First[i][a[j]]=j;
exist[i].push_back(a[j]);
}
Last[i][a[j]]=j;
}
for(int x=1; x<=BCC; x++)
for(int y=x; y<=BCC; y++)
for(int i=0; i<exist[x].size(); i++)
cal[x][y]=max(cal[x][y],Last[y][exist[x][i]]-First[x][exist[x][i]]);
for(int len=1; len<=BCC; len++)
for(int i=1; i+len-1<=BCC; i++) {
int j=i+len-1;
f[i][j]=max(max(f[i+1][j],f[i][j-1]),cal[i][j]);
}
for(int i=1; i<=BCC; i++)
for(int j=1; j<=m; j++)
LMax[i][j]=max(LMax[i-1][j],Last[i][j]);
memset(RMax,0x3f,sizeof(RMax));
for(int i=BCC; i>=1; i--)
for(int j=1; j<=m; j++)
RMax[i][j]=min(RMax[i+1][j],First[i][j]);
for(int i=1; i<=k; i++) {
int x=Get_Int(),y=Get_Int(),cnt=BCC+1;
int L=Belong[x],R=Belong[y],st=L,ed=R;
if(L==R) {
st=BCC+3;
ed=0;
L=R=cnt;
build(cnt++,x,y);
} else {
if(x!=Left[Belong[x]]) {
st=L+1;
L=cnt;
build(cnt++,x,Right[Belong[x]]);
}
if(y!=Right[Belong[y]]) {
ed=R-1;
R=cnt;
build(cnt++,Left[Belong[y]],y);
}
}
int ans=f[st][ed];
for(int i=0; i<exist[L].size(); i++)
ans=max(ans,Last[R][exist[L][i]]-First[L][exist[L][i]]);
if(R>BCC)
for(int i=0; i<exist[R].size(); i++)
ans=max(ans,Last[R][exist[R][i]]-RMax[st][exist[R][i]]);
if(L>BCC)
for(int i=0; i<exist[L].size(); i++)
ans=max(ans,LMax[ed][exist[L][i]]-First[L][exist[L][i]]);
printf("%d\n",ans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~