题目简述：
一个 $n \times n$ 的棋盘上面有 $n$ 个棋子，每行每列恰好有一个棋子，给定棋子的位置，求有多少个 $k \times k$ 的子棋盘上恰好有 $k$ 个棋子。$n ≤ 3 \times 10^{5}$。
思路：
限制是解决题目的突破口，「每行每列恰好有一个棋子」就是这道题中很好的限制。由于这个限制的存在，我们可以构造一个数列 $|a_{n}|$，对于每一个点 $(x,y)$ 命 $a_{x}=y$。这样就将原题中二维空间的问题转化成了一维空间中的问题：「 $|a_{n}|$ 中有多少个区间中的数字是连续的」或者说「 $|a_{n}|$ 中有多少个区间，满足 $max-min = r-l$ 」。
记一个区间的中点为 $mid$，我们可以将一个区间的答案分成三部分：$mid$ 左边，$mid$ 右边，和跨越 $mid$。前两个是区间从中间劈开所产生的子问题，可以递归解决，我们着重考虑一下第三部分。
预处理两个数组 $mx[\ i\ ]$ 和 $mn[\ i\ ]$，分别表示 $mid$ 到 $i$ 这一个区间的最大值和最小值。对于刚才提到的第三部分，我们又可以将它分成两种情况：「最大值和最小值在 $mid$ 的同一侧」和「最大值和最小值在 $mid$ 的两侧」。
如果最大值和最小值在同一侧 (不妨设都在左侧) ，此时整个区间的最大值和最小值都是左侧的最大值和最小值。根据题意，合法的区间满足 $mx[i]-mn[i]=j-i$，移项可得 $j=i+mx[i]-mn[i]$。此时我们发现 $j$ 只与 $i$ 以及 $i$ 那一侧的最值有关，所以只需要枚举 $i$ 就可以确定可以和他构成合法区间的 $j$。当然最值都在右侧同理，我们可以得到 $i=j-mx[j]+mn[j]$。
// If the max and min value are both on the left:
for(int i = mid; i>=l; i--){
int j = mx[i] - mn[i] + i;
if(j <= r && j > mid && mx[i] > mx[j] && mn[i] < mn[j]) ans++;
}
如果最大值和最小值在两侧 (不妨设最小值在左侧，最大值在右侧)，根据题意，合法的区间满足 $mx[j]-mn[i]=j-i$，移项得 $mn[i]-i=mx[j]-j$。问题变得棘手起来了：上面的分析的第一种情况，当 $i$ 确定时可以直接计算出一个 $j$ 是使等式成立，但是这里当 $i$ 确定时右边的 $j$ 还是不确定的，即每次扫描一个 $j$，$mx[j]$ 都会变。看上去只能暴力 $O(n^{2})$ 枚举左右端点，其实不然。因为对于一个固定的 $i$，若在某一时刻出现 $mn[j]<mn[i]$ 的情况 (不满足题意)，则无论 $j$ 再怎么扫描，对于扫描到的新点 $j’$ 一定有 $mn[j]’<mn[j]<mn[i]$，即之后的方案一定不合法。这样我们就没有继续枚举下去的必要了，只要在第一次出现不合法方案的时候及时跳出就可以了。对于固定的 $j$ 也是一样，若某一时刻出现 $mx[i]>mx[j]$，则之后的方案一定不合法。
具体该怎么实现呢？我们对于每一种符合题意时等式两边相等的那个值开一个桶，虽然那个值是 $|a_{n}|$ 数列上的位置加上 (或减去) 值，但是由于位置和值都是 $[1,n]$ 范围内的，所以桶的大小不会超过 $2n$。定义三个指针 $i,j,k$，其中 $i$ 是左边的位置，$j$ 和 $k$ 是右边的位置。若枚举到一个 $j$ 有$mn[j]>mn[i]$ (不满足 $mn[j]<mn[i]$ 的约束条件了)，就让 $bucket[mx[j]-j+n]++$，值得注意的是，这里加上 $n$ 是为了防止出现负的下标，由于所有减去的情况都加上了 $n$，所以在修改答案的时候是不会有影响的。$k$ 指针的作用是为了满足另一个约束条件 $mx[j]>mx[i]$。如果某一时刻有 $mx[k]<mx[i]$，那么即使这个位置的 $j$ 使得 $mn[j]<mn[i]$，也不是一个合法的方案。使用 $j$ 指针更新答案的时候我们并没有考虑另一个条件，所以现在我们要把只满足一个条件而不满足另一个条件的方案减掉，即让 $bucket[mx[k]-k+n]–$。
// If the min value is on the left while the max value is on the right:
// We should have "mn[i] - i == mx[j] - j" now.
j = k = mid+1;
for(i = mid; i>=l; i--){
while(j <= r && mn[j] > mn[i]){
bucket[mx[j]-j+n]++;
j++;
}
// Why do we stop once mn[j] is not greater than mn[i]?
// Because in this condition, mn[j] have been in the right part of segment, so the mn[j] will always less than mn[i].
while(k < j && mx[k] < mx[i]){
bucket[mx[k]-k+n]--;// By the way we'd better plus n to prevent mx[k]-k from being negative.
k++;
}
ans += bucket[mn[i]-i+n];
}
// Clear bucket.
while(k < j){
bucket[mx[k]-k+n]--;
k++;
}
上面只分析了最小值在左侧最大值在右侧的情况，但是翻过来也是一样的。记得及时更新 $ans$ 并清空桶。
Code：
//AC?
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<utility>
#define int long long
using namespace std;
const int MaxN = 300005;
int n, a[MaxN];
int mn[MaxN], mx[MaxN], bucket[MaxN*2], ans;
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void Divide_and_Conquer(int l, int r){
if(l == r) return (void)ans++;
int mid = (l+r)/2;
Divide_and_Conquer(l, mid);
Divide_and_Conquer(mid+1, r);
mx[mid] = mn[mid] = a[mid];
mx[mid+1] = mn[mid+1] = a[mid+1];
int i, j, k;
// Initiate part: calcutale max and min value from middle to the two border.
for(i = mid-1; i>=l; i--){
mx[i] = max(mx[i+1], a[i]);
mn[i] = min(mn[i+1], a[i]);
}
for(j = mid+2; j<=r; j++){
mx[j] = max(mx[j-1], a[j]);
mn[j] = min(mn[j-1], a[j]);
}
// If the max and min value are both on the left:
for(i = mid; i>=l; i--){
j = mx[i] - mn[i] + i;
if(j <= r && j > mid && mx[i] > mx[j] && mn[i] < mn[j]) ans++;
}
// If the max and min value are both on the right:
for(j = mid+1; j<=r; j++){
i = j - mx[j] + mn[j];
if(i <= mid && i >= l && mx[j] > mx[i] && mn[j] < mn[i]) ans++;
}
// If the min value is on the left while the max value is on the right:
// We should have "mn[i] - i == mx[j] - j" now.
j = k = mid+1;
for(i = mid; i>=l; i--){
while(j <= r && mn[j] > mn[i]){
bucket[mx[j]-j+n]++;
j++;
}
// Why do we stop once mn[j] is not greater than mn[i]?
// Because in this condition, mn[j] have been in the right part of segment, so the mn[j] will always less than mn[i].
while(k < j && mx[k] < mx[i]){
bucket[mx[k]-k+n]--;// By the way we'd better plus n to prevent mx[k]-k from being negative.
k++;
}
ans += bucket[mn[i]-i+n];
}
// Reset bucket, j and k.
while(k < j){
bucket[mx[k]-k+n]--;
k++;
}
i = k = mid;
// If the min value is on the right while the max value is on the left:
// We should have "mx[i] - i == mn[j] - j" now.
for(j = mid+1; j<=r; j++){
while(i >= l && mn[i] > mn[j]){
bucket[mx[i]+i]++;
i--;
}
while(k > i && mx[k] < mx[j]){
bucket[mx[k]+k]--;
k--;
}
ans += bucket[mn[j]+j];
}
// Reset again.
while(k > i){
bucket[mx[k]+k]--;
k--;
}
}
signed main(){
n = Read();
for(int i=1; i<=n; i++){
int u = Read(), v = Read();
a[u] = v;
}
Divide_and_Conquer(1, n);
printf("%lld\n", ans);
return 0;
}