【模板】笛卡尔树(Cartesian Tree) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> p(n + 1), ls(n + 1, 0), rs(n + 1, 0), stk(n + 1, 0);
    int top = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        int k = top;
        while (k > 0 && p[stk[k]] > p[i]) --k;
        if (k > 0) rs[stk[k]] = i;
        if (k < top) ls[i] = stk[k + 1];
        stk[++k] = i;
        top = k;
    }
    long long ansL = 0, ansR = 0;
    for (int i = 1; i <= n; ++i) {
        ansL ^= 1LL * i * (ls[i] + 1);
        ansR ^= 1LL * i * (rs[i] + 1);
    }
    cout << ansL << " " << ansR << "\n";
    return 0;
}