题目大意
由于各种原因，桐人现在被困在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;
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];
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;
}
|
