首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#12843

图书馆 题目描述 某城市有 n 条东西向街道和 n 条南北向街道,构成一个 n×n 的街区网格。每个交叉路口处恰好建有一座图书馆,且每一行、每一列的交叉路口都恰…

图书馆

题目描述

某城市有 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

输入保证每行每列恰好有一座图书馆。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;stack&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; vector&lt;int&gt; a, leftBig, rightBig; ll total = 0; void dfs(int l, int r, int mid) {     int maxVal = a[mid];     vector&lt;int&gt; minLeft, minRight;     int mn = maxVal;     minLeft.push_back(mn);     for (int i = mid - 1; i &gt;= l; i--) {         mn = min(mn, a[i]);         minLeft.push_back(mn);     }     mn = maxVal;     minRight.push_back(mn);     for (int i = mid + 1; i &lt;= 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 &lt;= L &amp;&amp; j &lt;= 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] &lt; minRight[j+1]) i++;         else j++;     }     int lm = leftBig[mid], rm = rightBig[mid];     if (lm &gt;= l) dfs(l, mid-1, lm);     if (rm &lt;= r) dfs(mid+1, r, rm); } int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin &gt;&gt; n;     vector&lt;int&gt; x(n), y(n);     a.resize(n+2);     leftBig.assign(n+2, 0);     rightBig.assign(n+2, n+1);     for (int i = 0; i &lt; n; i++) cin &gt;&gt; x[i];     for (int i = 0; i &lt; n; i++) cin &gt;&gt; y[i];     for (int i = 0; i &lt; n; i++) a[x[i]] = y[i];     stack&lt;int&gt; st;     for (int i = 1; i &lt;= n; i++) {         while (!st.empty() &amp;&amp; a[st.top()] &lt; a[i]) st.pop();         if (!st.empty()) leftBig[i] = st.top();         st.push(i);     }     while (!st.empty()) st.pop();     for (int i = n; i &gt;= 1; i--) {         while (!st.empty() &amp;&amp; a[st.top()] &lt; a[i]) st.pop();         if (!st.empty()) rightBig[i] = st.top();         st.push(i);     }     int root = 1;     for (int i = 2; i &lt;= n; i++) if (a[i] &gt; a[root]) root = i;     dfs(1, n, root);     total += n;     cout &lt;&lt; total &lt;&lt; endl;     return 0; }</pre>
解析

输出应该是9,题目给出的输出为10,貌似有错误。