笛卡尔树 - OI Wiki

用来 $O(n)$ 访问查询多次区间最值的数据结构，数中每个节点存在 $(k,w)$ ， $k$ 符合二叉搜索树的特性，左边值小于节点右边值大于节点， $w$ 符合堆的特性，节点值小于(大于)全部的子节点。

最大子矩形

我们把每个矩形的下标当作 $k$ ，矩形高度 $h_i$ 当作 $w$ ，构造出笛卡尔树，从上到下求解树形 $dp$ 即可。

我们构造的笛卡尔树满足左右区间连续。
我们构造的笛卡尔树满足当前节点的高度一定小于它全部的子节点。

所以我们从根(最小的高度)出发，求解 $(sz+1)*h_u$ 取最大值就是答案了。 $sz$ 代表当前节点的子节点个数。

那么我们还能稍加变形，如果给出的矩形宽度不是 $1$ ，而是 $p_i$ ，我们也可以使用树形 $dp$ 求解全部子节点的宽度，返回到父节点那里去。

const int N = 1e5 + 7;
ll n, m;
int a[N];
int st[N], top, ls[N], rs[N];

void build() {
    top = 0;
    rep(i, 1, n) {
        int k = top;
        while (k > 0 and a[st[k]] > a[i])    --k;
        if (k)    rs[st[k]] = i;
        if (k < top)    ls[i] = st[k + 1];
        st[++k] = i;
        top = k;
    }
}

ll ans;

int dfs(int x) {
    if (!x)    return 0;
    int sz = dfs(ls[x]) + dfs(rs[x]) + 1;
    ans = max(ans, 1ll * sz * a[x]);
    return sz;
}

void solve() {
    fill(ls + 1, ls + 1 + n, 0);
    fill(rs + 1, rs + 1 + n, 0);
    rep(i, 1, n)    a[i] = read();
    build();
    ans = 0;
    dfs(st[1]);
    print(ans);
}

H-Sort the Strings Revision

现在你初始的字符串是 $01234567890123...$ 这样的 $x_i=i\%10$ 的字符串。

现在你有 $n$ 次操作，每次可以把第 $p_i$ 个位置原本的字符串改成 $d_i$ ，并且这里相当于生成了一个新的字符串，并且保证位置 $p_i$ 唯一。

你要把这 $n$ 个新生成的字符串和原本初始的字符串一起按照字典序排序后，求解到每个字符串在字典序中的 $rk[i]$ 。

最终输出 $(\sum\limits_{i=0}^n rk[i]*10000019^i)\%1e9+7$ 。

不难发现因为给出的我们 $p_i$ 是唯一的，所以对于每次修改后的字符串，前后一定是存在明显分层的。

还有一种情况没有考虑那就是对于修改 $p_i$ 位置之后没改变的，那就按照从上到下的操作顺序打上编号就行。这里引用一下Zc_Ethan的图片。

在这里插入图片描述

我们每次求解到 $[l,r]$ 的最小值在哪里，从哪里分层即可，这个求解只能用笛卡尔树 $O(n)$ ，其他区间最值都被卡的比较死，卡常比较艰难。

const int N = 2e6 + 7;
ll n, m;
ll p[N], d[N];
int st[N], top, ls[N], rs[N];
ll pw[N];

void build() {
    top = 0;
    rep(i, 0, n - 1) {
        int k = top;
        while (k > 0 and p[st[k]] > p[i])    --k;
        if (k)    rs[st[k]] = i;
        if (k < top)    ls[i] = st[k + 1];
        st[++k] = i;
        top = k;
    }
}

int rk[N], tot;
void dfs(int x, int left, int right) {
    if (left > right)    return;
    if (left == right) {
        rk[left] = tot++;
        return;
    }
    if (p[x] == INF64) {
        rep(i, left, right)
            rk[i] = tot++;
        return;
    }
    if (p[x] % 10 > d[x]) {
        dfs(rs[x], x + 1, right);
        dfs(ls[x], left, x);
    }
    else {
        dfs(ls[x], left, x);
        dfs(rs[x], x + 1, right);
    }
}

void solve() {
    n = read();
    fill(ls + 1, ls + 1 + n, 0);
    fill(rs + 1, rs + 1 + n, 0);
    tot = 0;
    ll sa = read(), a = read(), b = read(), mod = read();
    rep(i, 0, n - 1)    p[i] = i;
    rep(i, 1, n - 1)    swap(p[sa % (i + 1)], p[i]), sa = (sa * a + b) % mod;
    sa = read(), a = read(), b = read(), mod = read();
    rep(i, 0, n - 1)    d[i] = sa % 10, sa = (sa * a + b) % mod;
    rep(i, 0, n - 1)    if (p[i] % 10 == d[i])    p[i] = INF64;
    build();
    dfs(st[1], 0, n);
    ll ans = 0;
    rep(i, 0, n)    ans = (ans + rk[i] * pw[i] % MOD) % MOD; // pw[]就预处理一下
    print(ans);
}