A17495. 图书馆
填空题
困难
知识点
题目描述
图书馆
题目描述
某城市有 n 条东西向街道和 n 条南北向街道，构成一个 n×n 的街区网格。每个交叉路口处恰好建有一座图书馆，且每一行、每一列的交叉路口都恰好有一座图书馆。已知第 i 座图书馆的坐标 (xi,yi) 表示它位于第 xi 条东西向街道与第 yi 条南北向街道的交汇处。
城市规划师想要知道：有多少个 正方形区域（由连续的若干条东西向街道和连续的若干条南北向街道围成），使得该区域内每一行、每一列也恰好各有一座图书馆？
输入格式
第一行，一个整数 n。
第二行，n 个整数 x1,x2,…,xn，表示第 i 座图书馆的东西向街道编号。
第三行，n 个整数 y1,y2,…,yn，表示第 i 座图书馆的南北向街道编号。
输入保证：1≤xi,yi≤n，且每行每列恰好只有一座图书馆。
输出格式
输出一个整数，表示满足条件的正方形区域个数。
输入样例
7
1 2 3 4 5 6 7
4 3 1 6 2 5 7输出样例
10说明提示
1≤n≤105
1≤xi,yi≤n
输入保证每行每列恰好有一座图书馆。
参考答案
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<int> a, leftBig, rightBig;
ll total = 0;
void dfs(int l, int r, int mid) {
int maxVal = a[mid];
vector<int> minLeft, minRight;
int mn = maxVal;
minLeft.push_back(mn);
for (int i = mid - 1; i >= l; i--) {
mn = min(mn, a[i]);
minLeft.push_back(mn);
}
mn = maxVal;
minRight.push_back(mn);
for (int i = mid + 1; i <= r; i++) {
mn = min(mn, a[i]);
minRight.push_back(mn);
}
int L = minLeft.size() - 1;
int R = minRight.size() - 1;
int i = 0, j = 0;
while (i <= L && j <= R) {
int curMin = min(minLeft[i], minRight[j]);
if (maxVal - curMin == i + j) total++;
if (i == L) j++;
else if (j == R) i++;
else if (minLeft[i+1] < minRight[j+1]) i++;
else j++;
}
int lm = leftBig[mid], rm = rightBig[mid];
if (lm >= l) dfs(l, mid-1, lm);
if (rm <= r) dfs(mid+1, r, rm);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> x(n), y(n);
a.resize(n+2);
leftBig.assign(n+2, 0);
rightBig.assign(n+2, n+1);
for (int i = 0; i < n; i++) cin >> x[i];
for (int i = 0; i < n; i++) cin >> y[i];
for (int i = 0; i < n; i++) a[x[i]] = y[i];
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (!st.empty()) leftBig[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (!st.empty()) rightBig[i] = st.top();
st.push(i);
}
int root = 1;
for (int i = 2; i <= n; i++) if (a[i] > a[root]) root = i;
dfs(1, n, root);
total += n;
cout << total << endl;
return 0;
}
上一题
下一题