题意
给定一个全排列\(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);
}