笛卡尔树 - OI Wiki

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

最大子矩形

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

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

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

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

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

现在你初始的字符串是这样的的字符串。

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

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

最终输出。

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

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

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

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);
}