P3793 由乃救爷爷

题意

给定一个长度为 \(n\) 的序列（\(1 \le n \le 2 \times 10 ^ 7\)），对于每组询问 \([l, r]\)，找到其区间最大值，并进行累加。

思路

\(n\) 太大，不能用 ST 表/线段树，考虑以下表为键值，数值为优先级建出笛卡尔树。

对于左右两个端点 \([l, r]\)，我们从笛卡尔树顶端往下跑，找到一个 \(l \le x \le r\) 的点 \(x\)，输出其对应的结果即可。

代码

#include <bits/stdc++.h>

using namespace std;
using ull = unsigned long long;

const int N = 20000010;

int lc[N], rc[N], stk[N], top;
int n, m, s, a[N];

//Problem Statement

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

// Problem Statement(end)

int main() {
    cin >> n >> m >> s;
    srand(s);
    for (int i = 1; i <= n; i++) a[i] = read();

    for (int i = 1; i <= n; i++) {
        int k = top;
        while (k && a[stk[k]] < a[i]) k--;
        if (k) rc[stk[k]] = i;
        if (k < top) lc[i] = stk[k + 1];
        stk[++k] = i;
        top = k;
    }

    int rt = stk[1];

    ull ans = 0;
    while (m--) {
        int l = read() % n + 1, r = read() % n + 1;
        if (l > r) swap(l, r);
        int x = rt;
        int res = 0;
        while (true) {
            if (x >= l && x <= r) {
                res = a[x];
                break;
            }
            if (x < l) {
                if (rc[x]) x = rc[x];
                else break;
            }
            if (x > r) {
                if (lc[x]) x = lc[x];
                else break;
            }
        }
        ans += res;
    }
    cout << ans << '\n';
    return 0;
}