Codeforces 1156E Special Segments of Permutation
题目链接
https://codeforces.com/contest/1156/problem/E
题目大意
给你一个长度为 $n$ 的排列 $p$ ，问满足 $p_l + p_r = \max \limits_{i = l}^{r} p_i$ 的连续子序列 $p[l, r]$ 有多少种。
题目分析
考虑使用分治来解决本题。对于一个区间，左右区间内对答案的贡献计算出来之后，考虑如何解决跨区间的问题。由于询问的一直是左右端点和最大值的关系，因此可以采用两个指针在左侧和右侧扫描，如果比最大值小那么就可以扩展区间，扩展的同时记录是否可以构造出最大值，如果两个指针所指向的全部都大于当前最大值，选择更小的那个数拓展区间即可。这样显然每个最大值所能影响到的几个端点都能覆盖到，因此最终可以求得总和。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, t;
int a[maxn];
int visl[maxn];
int visr[maxn];
long long ans = 0;
int read(){
int x;
scanf("%d", &x);
return x;
}
int dfs(int l, int r){
int x, y;
int mid = (l + r) / 2;
int maxx = 0;
if(l == r)return 0;
dfs(l, mid);
dfs(mid + 1, r);
x = mid, y = mid + 1;
maxx = max(a[x], a[y]);
visl[a[x]] = 1;
visr[a[y]] = 1;
while(true){
while(x - 1 >= l and a[x - 1] <= maxx){
x--;
visl[a[x]]++;
ans += visr[maxx - a[x]];
}
while(y + 1 <= r and a[y + 1] <= maxx){
y++;
visr[a[y]]++;
ans += visl[maxx - a[y]];
}
if(l == x and y == r)break;
if(x - 1 < l){
y++;
visr[a[y]]++;
maxx = max(maxx, a[y]);
}else if(y + 1 > r){
x--;
visl[a[x]]++;
maxx = max(maxx, a[x]);
}else if(a[x - 1] > a[y + 1]){
y++;
visr[a[y]]++;
maxx = max(maxx, a[y]);
}else if(a[x - 1] < a[y + 1]){
x--;
visl[a[x]]++;
maxx = max(maxx, a[x]);
}else{
y++;
visr[a[y]]++;
maxx = max(maxx, a[y]);
x--;
visl[a[x]]++;
maxx = max(maxx, a[x]);
}
}
for(int i=l;i<=r;i++){
visl[a[i]] = 0;
visr[a[i]] = 0;
}
return 0;
}
int main(){
int i, j;
n = read();
for(i=1;i<=n;i++){
a[i] = read();
}
dfs(1, n);
printf("%lld\n", ans);
return 0;
}