CF1156E Special Segments of Permutation

爱被打了一巴掌 2021-12-20 10:29 182阅读 0赞

[CF1156E Special Segments of Permutation][]

> 给定一个长度为 \\(n\\) 的排列，求有多少个区间 \\(\[l,\\ r\]\\) 使得 \\(a\_l+a\_r=\\displaystyle\\max\_\{i=l\}^r\\\{a\_i\\\}\\)
> 
> \\(n\\leq2\\times10^5\\)

单调栈，暴力，启发式合并

--------------------

考虑枚举每个数作为最大值出现的区间 \\(\[l\_i,\\ r\_i\]\\) ，可以用单调栈 \\(O(n)\\) 求出

对于区间 \\(\[l\_i,\\ r\_i\]\\) ，考虑枚举左端点 \\(l\\) ，可以求出右端点元素 \\(a\_r=a\_i-a\_l\\) ，若 \\(r\\in\[i,\\ r\]\\) ，则计入贡献

但这样是 \\(O(n^2)\\) 的

考虑一个看似无用的优化：每次枚举 \\(\[l,\\ i\],\\ \[i,\\ r\]\\) 较短的一侧

考虑这样的时间复杂度：对原排列建树，对区间 \\(\[l,\\ r\]\\) 将区间最大值 \\(a\_i\\) 作为根，两侧递归。这样点 \\(i\\) 所遍历的点数即为 \\(\\min(\\operatorname\{size(lson),\\ size(rson)\})\\) ，可以采用启发式合并的时间复杂度证明

时间复杂度 \\(O(n\\log n)\\)

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int n, top, a[maxn], st[maxn], pos[maxn], lef[maxn], rig[maxn]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", a + i), pos[a[i]] = i; } for (int i = 1; i <= n; i++) { while (top && a[st[top]] < a[i]) top--; lef[i] = st[top] + 1, st[++top] = i; } top = 0, st[0] = n + 1; for (int i = n; i; i--) { while (top && a[st[top]] < a[i]) top--; rig[i] = st[top] - 1, st[++top] = i; } int ans = 0; for (int i = 1; i <= n; i++) { int l = lef[i], r = rig[i]; if (i - l < r - i) { for (int j = l; j <= i; j++) { ans += pos[a[i] - a[j]] >= i && pos[a[i] - a[j]] <= r; } } else { for (int j = i; j <= r; j++) { ans += pos[a[i] - a[j]] >= l && pos[a[i] - a[j]] <= i; } } } printf("%d", ans); return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/11042187.html

[CF1156E Special Segments of Permutation]: https://codeforces.com/problemset/problem/1156/E