牛牛的最美味和最不美味的零食

参考Severus.的题解

思路

• 除了$max\mathrm{和}minmax和min$，结点还维护一个当前区间有效的零食的数量$cntcnt$，例如区间[1,5]吃掉了零食2，那么区间[1,5]的$cnt=5-1=4cnt=5-1=4$
• 修改操作modify(int u, int k)：表示将当前u结点的区间的第k个有效元素删除。记左儿子的区间中有效个数为$lcntlcnt$，如果$lcnt\ge klcnt\; \backslash ge\; k$，则递归删除左儿子的第k个有效元素；如果，则递归删除右儿子的第$k-lcntk-lcnt$个有效元素
• 查询操作query(int u, int l, int r)：表示查询当前结点u的区间的第$ll$到第$rr$个有效元素中的最值。当前区间为$[1,u\mathrm{.}cnt][1,u.cnt]$，如果$[1,u\mathrm{.}cnt]\subset [l,r]\mathrm{，}\mathrm{即}l\le 1\mathrm{且}r\ge u\mathrm{.}cnt[1,u.cnt]\; \backslash subset\; [l,\; r]，即l\; \backslash le\; 1且r\backslash ge\; u.cnt$，直接返回当前区间的最值；记左儿子的区间中有效个数为$lcntlcnt$，如果$l\le lcntl\backslash le\; lcnt$，递归查询左儿子的第$l\mathrm{到}\mathrm{第}r\mathrm{个}\mathrm{元}\mathrm{素}\mathrm{的}\mathrm{最}\mathrm{值}l到第r个元素的最值$，如果$r>lcntr>lcnt$，递归查询右儿子区间的$[l-lcnt,r-lcnt][l-lcnt,r-lcnt]$中的最值

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e6 + 10, INF = 2e9;
int n, m;
int a[N];
struct Node
{
    int l, r;
    int cnt, mx, mn;
} tr[N * 4];

void pushup(int u)
{
    tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if (l == r)
    {
        tr[u].cnt = 1;
        tr[u].mx = tr[u].mn = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

// 表示将当前u结点的区间的第k个元素删除
void modify(int u, int k)
{
    if (tr[u].l == tr[u].r)
    {
        tr[u].cnt = 0;
        tr[u].mx = -INF;
        tr[u].mn = INF;
        return;
    }
    int lcnt = tr[u << 1].cnt;
    if (k <= lcnt)
        modify(u << 1, k);
    else
        modify(u << 1 | 1, k - lcnt); // 将右儿子的区间的第k-lcnt个元素删除
    pushup(u);
}

// 查询当前结点u代表区间的[l,r]中的最值
PII query(int u, int l, int r)
{
    if (l <= 1 && r >= tr[u].cnt)
    {
        return make_pair(tr[u].mx, tr[u].mn);
    }
    int lcnt = tr[u << 1].cnt;
    PII a = {-INF, INF}, b = {-INF, INF};
    if (l <= lcnt)
        a = query(u << 1, l, r);
    if (r > lcnt)
        b = query(u << 1 | 1, l - lcnt, r - lcnt);
    return make_pair(max(a.first, b.first), min(a.second, b.second));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    while (m--)
    {
        int op, l, r, k;
        cin >> op;
        if (op == 1)
        {
            cin >> k;
            modify(1, k);
        }
        else
        {
            cin >> l >> r;
            PII res = query(1, l, r);
            cout << res.second << ' ' << res.first << '\n';
        }
    }
    return 0;
}