笛卡尔树，学术求问

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 1e2;
int n,s[N],l[N],r[N],f[N],k;
long long ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) {
        cin >> s[i];
        if(s[i] > s[i - 1]) {
            r[i - 1] = i;
            f[i] = i - 1;
            continue;
        }
        k = i - 1;
        while(s[f[k]] > s[i]) k = f[k];
        l[i] = k;
        f[i] = f[k];
        r[f[k]] = i;
        f[k] = i;
    }
    for(int i = 1;i <= n;i ++) ans ^= (long long)(1ll * i * (l[i] + 1));
    cout << ans << ' ';
    ans = 0;
    for(int i = 1;i <= n;i ++) ans ^= (long long)(1ll * i * (r[i] + 1));
    cout << ans << '\n';
    return 0;
}