题意
给定一个全排列\(a\)。
定义子区间\([l,r]\),当且仅当\(a_l + a_r = Max[l,r]\)。
求\(a\)序列中子区间的个数。
题解
笛卡尔树上的启发式合并。
\(2000MS\)的时限，\(1965MS\)卡过。。
还可以不建树，直接枚举区间，就可以用数组维护了。这种做法比较快。
代码
#include <bits/stdc++.h>
#define FOPI freopen("in.txt", "r", stdin)
#define FOPO freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 100;
int n;
int a[maxn];
int ch[maxn][2], fa[maxn];
map<int, int> M[maxn];
LL ans = 0;
void build_Dkr()
{
stack<int> ST;
int tmp;
for (int i = 1; i <= n; i++) {
if (!ST.empty() && a[ST.top()] < a[i]) {
while(!ST.empty() && a[ST.top()] < a[i]) {
tmp = ST.top();
ST.pop();
}
ch[i][0] = tmp;
fa[tmp] = i;
}
if (!ST.empty()) {
ch[ST.top()][1] = i;
fa[i] = ST.top();
}
ST.push(i);
}
}
void merge(int x, int y, int Max)
{
if (M[x].size() < M[y].size())
swap(M[x], M[y]);
for (auto val : M[y]) {
int a = val.first, b = val.second;
ans += 1ll * b * M[x][Max-a];
}
for (auto val : M[y]) {
int a = val.first, b = val.second;
M[x][a] += b;
}
M[y].clear();
}
void dfs(int x)
{
for (int i = 0; i < 2; i++) {
if (ch[x][i] == 0) continue;
dfs(ch[x][i]);
merge(x, ch[x][i], a[x]);
}
}
int main()
{
// FOPI;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
M[i][a[i]] = 1;
}
build_Dkr();
for (int i = 1; i <= n; i++) {
if (fa[i] == 0) {
dfs(i);
break;
}
}
printf("%lld\n", ans);
}