https://codeforces.com/contest/1156/problem/E
题目大意
给出 $n$ 长的排列 $p$。问其中有多少 $l, r$ 子段满足 $p_l + p_r = \max_{i = l}^{r} p_i$。
$3 \le n \le 2 \times 10^5$。$1 \le p_i \le n$ 且不重复。
简要题解
因为涉及到区间最值，想到笛卡尔树。建出最大值为根的笛卡尔树之后相当于问，左界在左子树中，右界在右子树中且对应节点加和为当前子树的根的值的对有多少。后面这件事显然可以启发式合并。
复杂度
$T$：$O(n \log^2 n)$ 时间给的比较松（$2s$）不然还这不太敢写这个做法。跑了 $531ms$，比标答慢不少。
$S$：$O(n \log n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> p(n);
for (int& i : p) cin >> i;
vector<int> l(n, -1), r(n, -1);
stack<int> st;
int rt = 0;
for (int i = 0; i < n; i++) {
int ls = -1;
while (!st.empty() && p[st.top()] < p[i]) {
ls = st.top(); st.pop();
}
if (st.empty()) {
rt = i;
} else {
r[st.top()] = i;
}
l[i] = ls;
st.push(i);
}
// cerr << "rt " << rt << endl;
// for (int i = 0; i < n; i++) {
// cerr << i << ' ' << l[i] << ' ' << r[i] << endl;
// }
int ans = 0;
vector<set<int>> se(n);
auto merge = [&](int u, int v, int tar) -> void {
if (se[u].size() < se[v].size()) {
swap(se[u], se[v]);
}
for (int i : se[v]) {
if (se[u].count(tar - i)) ans++;
}
for (int i : se[v]) {
se[u].insert(i);
}
};
y_comb([&](auto dfs, int u) -> void {
if (u == -1) return;
dfs(l[u]);
dfs(r[u]);
if (l[u] != -1 && r[u] != -1) {
swap(se[u], se[l[u]]);
merge(u, r[u], p[u]);
} else if (l[u] != -1) {
swap(se[u], se[l[u]]);
} else if (r[u] != -1) {
swap(se[u], se[r[u]]);
}
se[u].insert(p[u]);
})(rt);
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
简要题解
除了笛卡尔树的部分，我们可以很容易的得出每棵子树的左右界。更进一步我们可以通过排列的逆排列得出每个元素的位置，在查询的时候只需看位置是不是在段里，这样就可以 $O(1)$ 处理了。
复杂度
$T$：$O(n \log n)$ 确实这个方法时间上好很多只跑了 $93ms$。
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> p(n);
for (int& i : p) cin >> i;
vector<int> l(n, -1), r(n, -1);
stack<int> st;
int rt = 0;
for (int i = 0; i < n; i++) {
int ls = -1;
while (!st.empty() && p[st.top()] < p[i]) {
ls = st.top(); st.pop();
}
if (st.empty()) {
rt = i;
} else {
r[st.top()] = i;
}
l[i] = ls;
st.push(i);
}
vector<int> pos(n + 1);
for (int i = 0; i < n; i++) {
pos[p[i]] = i;
}
int ans = 0;
y_comb([&](auto dfs, int u) -> PII {
if (l[u] != -1 && r[u] != -1) {
PII ls = dfs(l[u]);
PII rs = dfs(r[u]);
int il = ls.first, ir = ls.second;
int jl = rs.first, jr = rs.second;
if (ls.second - ls.first > rs.second - rs.first) {
swap(il, jl);
swap(ir, jr);
}
for (int i = il; i <= ir; i++) {
int v = (p[u] - p[i]);
if (jl <= pos[v] && pos[v] <= jr) ans++;
}
return {ls.first, rs.second};
} else if (l[u] != -1) {
PII ls = dfs(l[u]);
return {ls.first, u};
} else if (r[u] != -1) {
PII rs = dfs(r[u]);
return {u, rs.second};
} else {
return {u, u};
}
})(rt);
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. 0-1-Tree - Educational Codeforces Round 64 (Rated for Div. 2)