算法1

美哉我线段树，壮哉我线段树

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1000010, INF = 0x3f3f3f3f;
struct Node{
    int l, sz;
    int minv, maxv;
}tr[N * 4];

int n, m;

int w[N];

void pushup(int u)
{
    tr[u].sz = tr[u << 1].sz + tr[u << 1 | 1].sz;
    tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int sz)
{
    tr[u] = {l, sz};
    if(sz == 1)
    {
        tr[u].minv = tr[u].maxv = w[l];
        return;
    }
    int half = sz / 2;
    build(u << 1, l, half);
    build(u << 1 | 1, l + half, sz - half);
    pushup(u);
}

void modify(int u, int x)
{
    if(tr[u].sz == 1)
    {
        tr[u].sz = 0;
        tr[u].maxv = -INF;
        tr[u].minv = INF;
        return;
    }
    auto &l = tr[u << 1], &r = tr[u << 1 | 1];
    int d = r.l - l.l - l.sz;
    if(x < l.l + l.sz) modify(u << 1, x);
    else modify(u << 1 | 1, x + d);
    pushup(u);
}

PII query(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].l + tr[u].sz - 1)
    {
        return {tr[u].minv, tr[u].maxv};
    }
    auto &lv = tr[u << 1], &rv = tr[u << 1 | 1];
    PII res(INF, -INF);
    int d = rv.l - lv.l - lv.sz;
    if(l < lv.l + lv.sz) 
    {
        auto r1 = query(u << 1, l, r);
        res.x = min(res.x, r1.x);
        res.y = max(res.y, r1.y);
    }
    if(r >= lv.l + lv.sz)
    {
        auto r2 = query(u << 1 | 1, l + d, r + d);
        res.x = min(res.x, r2.x);
        res.y = max(res.y, r2.y);
    }
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    build(1, 1, n);
    while(m --)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int k;
            scanf("%d", &k);
            modify(1, k);
        }
        else 
        {
            int a, b;
            scanf("%d %d", &a, &b);
            auto res = query(1, a, b);
            printf("%d %d\n", res.x, res.y);
        }
    }
    return 0;
}