隐藏
「JZOJ4687」奇袭 - 分治+Hash | Bill Yang's Blog

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

0%

「JZOJ4687」奇袭 - 分治+Hash

题目大意

    由于各种原因,桐人现在被困在Under World(以下简称UW)中,而UW马上要迎来最终的压力测试——魔界入侵。
    唯一一个神一般存在的Administrator被消灭了,靠原本的整合骑士的力量是远远不够的。所以爱丽丝动员了UW全体人民,与整合骑士一起抗击魔族。
    在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前发动一次奇袭,袭击魔族大本营!
    为了降低风险,爱丽丝找到了你,一名优秀斥候,希望你能在奇袭前对魔族大本营进行侦查,并计算出袭击的难度。
    经过侦查,你绘制出了魔族大本营的地图,然后发现,魔族大本营是一个N×N的网格图,一共有N支军队驻扎在一些网格中(不会有两只军队驻扎在一起)。
    在大本营中,每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队,我们袭击的难度就会增加1点。
    现在请你根据绘制出的地图,告诉爱丽丝这次的袭击行动难度有多大。


题目分析

很显然,因为有条件:保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样的。
我们可以将整个平面图压缩序列:$a[x]=y$。

这样我们将平面图的问题转化为了序列问题,要求的答案即为满足$\max[i,j]-\min[i,j]=j-i$的方案数。

这样我们就可以使用$O(n^2)$的算法解决了。

然而依然会TLE,考虑如何优化。

我们曾经做过两道区间最值限制问题,都是使用的分治解决,考虑本题能否同样使用分治。

之前的两道题使用最值点分割,然后使用启发式合并/随机数据的方法优化,达到$O(n\log n)$的复杂度,但是本题有两个最值点,想要达到$O(n\log n)$的复杂度,应该考虑从中间分割区间。

如图,考虑从$mid$向$Left$枚举$i$,并利用数据结构维护$j$。

先预处理出从$mid$向两个方向的最大/最小前缀:$LMax[],RMax[],LMin[],RMin[]$

讨论四种情况。

  • 最大值点在左侧,最小值点在右侧

    此时的条件是:$LMax[i]\gt RMax[j],LMin[i]\gt RMin[j]$。
    此时有$LMax[i]-RMin[j]=j-i$,移项得:$i+LMax[i]=j+RMin[j]$。
    因此我们可以维护一个$Hash$表来统计根据下标$i+LMax[i]$查询答案。
    考虑如何维护$Hash$表:因为前缀具有单调性。

    设满足$LMax[i]\gt RMax[j]$的最靠右合法位置为指针$rpos$,而满足$LMin[i]\gt RMin[j]$的最靠左位置为指针$lpos$,则$j$可以取到的合法区间为$[lpos,rpos]$。
    因为指针$lpos,rpos$只会向右移动不会回退,因此当指针移动的时候对$Hash$表进行$++—$即可。
    注意,在统计答案的时候可能$lpos\gt rpos$,出现hash表是负数的情况,此时不计入答案。
  • 最大值点在右侧,最小值点在左侧
    与上一种情况类似
  • 最大值点/最小值点均在左侧

    此时的条件是:$LMax[i]\gt RMax[j],LMin[i]\gt RMin[j]$。
    此时$LMax[i]-LMin[i]=j-i$,移项得到$LMax[i]+i-LMin[i]=j$,也就是说$j$的位置可以直接计算得到,判断一下如果$j$的位置符合条件,则$ans++$。
  • 最大值点/最小值点均在右侧
    与上一种情况类似

处理完后递归左右子区间即可。


注意事项

$Hash$表的下标可能是负数,增加一个偏移量即可。


代码

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
#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,Delta=100000;
int n,LMin[maxn],LMax[maxn],RMin[maxn],RMax[maxn],a[maxn],Hash[maxn*4];
long long ans=0;
void Solve(int Left,int Right) {
if(Left==Right) {
ans++;
return;
}
int mid=(Left+Right)>>1;
for(int i=Left; i<=Right; i++)LMin[i]=RMin[i]=0x7fffffff/2,LMax[i]=RMax[i]=-0x7fffffff/2;
for(int i=mid; i>=Left; i--)LMin[i]=min(LMin[i+1],a[i]),LMax[i]=max(LMax[i+1],a[i]);
for(int i=mid+1; i<=Right; i++)RMin[i]=min(RMin[i-1],a[i]),RMax[i]=max(RMax[i-1],a[i]);
int l=mid+1,r=mid+1;
for(int i=mid; i>=Left; i--) {
int pos=LMax[i]-LMin[i]+i; //Max/Min左
if(pos>mid&&pos<=Right&&LMax[i]>=RMax[pos]&&LMin[i]<=RMin[pos])ans++;
while(r<=Right&&LMax[i]>=RMax[r]) {
Hash[r+RMin[r]]++;
r++;
}
while(l<=Right&&LMin[i]<RMin[l]) {
Hash[l+RMin[l]]--;
l++;
}
if(Hash[i+LMax[i]]>0)ans+=Hash[i+LMax[i]];
}
while(r>mid+1) {
r--;
Hash[r+RMin[r]]--;
}
while(l>mid+1) {
l--;
Hash[l+RMin[l]]++;
}
l=mid,r=mid;
for(int i=mid+1; i<=Right; i++) {
int pos=i-RMax[i]+RMin[i]; //Max/Min右
if(pos>=Left&&pos<=mid&&RMax[i]>=LMax[pos]&&RMin[i]<=LMin[pos])ans++;
while(l>=Left&&RMax[i]>=LMax[l]) {
Hash[LMin[l]-l+Delta]++;
l--;
}
while(r>=Left&&RMin[i]<LMin[r]) {
Hash[LMin[r]-r+Delta]--;
r--;
}
if(Hash[RMax[i]-i+Delta]>0)ans+=Hash[RMax[i]-i+Delta];
}
while(l<mid) {
l++;
Hash[LMin[l]-l+Delta]--;
}
while(r<mid) {
r++;
Hash[LMin[r]-r+Delta]++;
}
Solve(Left,mid);
Solve(mid+1,Right);
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int(),y=Get_Int();
a[x]=y;
}
Solve(1,n);
printf("%lld\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~