用C++写一个珂朵莉树的模板代码

以下是一个珂朵莉树的模板代码，供参考：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;

struct KDT {
    int l, r;
    int lazy;
    int minv, maxv;
} kdt[MAXN * 4]; // 线段树节点

int n, m;
int a[MAXN];

void pushup(int rt) {
    kdt[rt].minv = min(kdt[rt << 1].minv, kdt[rt << 1 | 1].minv);
    kdt[rt].maxv = max(kdt[rt << 1].maxv, kdt[rt << 1 | 1].maxv);
}

void pushdown(int rt) {
    if (kdt[rt].lazy != -1) {
        kdt[rt << 1].lazy = kdt[rt].lazy;
        kdt[rt << 1 | 1].lazy = kdt[rt].lazy;
        kdt[rt << 1].minv = kdt[rt].lazy;
        kdt[rt << 1].maxv = kdt[rt].lazy;
        kdt[rt << 1 | 1].minv = kdt[rt].lazy;
        kdt[rt << 1 | 1].maxv = kdt[rt].lazy;
        kdt[rt].lazy = -1;
    }
}

void build(int l, int r, int rt) {
    kdt[rt].l = l;
    kdt[rt].r = r;
    kdt[rt].lazy = -1;
    if (l == r) {
        kdt[rt].minv = kdt[rt].maxv = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

void update(int L, int R, int c, int rt) {
    if (L <= kdt[rt].l && kdt[rt].r <= R) {
        kdt[rt].lazy = c;
        kdt[rt].minv = c;
        kdt[rt].maxv = c;
        return;
    }
    pushdown(rt);
    int mid = (kdt[rt].l + kdt[rt].r) >> 1;
    if (L <= mid) update(L, R, c, rt << 1);
    if (R > mid) update(L, R, c, rt << 1 | 1);
    pushup(rt);
}

int query_min(int L, int R, int rt) {
    if (L <= kdt[rt].l && kdt[rt].r <= R) {
        return kdt[rt].minv;
    }
    pushdown(rt);
    int mid = (kdt[rt].l + kdt[rt].r) >> 1;
    int res = 2147483647;
    if (L <= mid) res = min(res, query_min(L, R, rt << 1));
    if (R > mid) res = min(res, query_min(L, R, rt << 1 | 1));
    return res;
}

int query_max(int L, int R, int rt) {
    if (L <= kdt[rt].l && kdt[rt].r <= R) {
        return kdt[rt].maxv;
    }
    pushdown(rt);
    int mid = (kdt[rt].l + kdt[rt].r) >> 1;
    int res = -2147483647;
    if (L <= mid) res = max(res, query_max(L, R, rt << 1));
    if (R > mid) res = max(res, query_max(L, R, rt << 1 | 1));
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int opt, l, r, c;
        cin >> opt >> l >> r;
        if (opt == 1) {
            cin >> c;
            update(l, r, c, 1);
        } else if (opt == 2) {
            cout << query_min(l, r, 1) << endl;
        } else {
            cout << query_max(l, r, 1) << endl;
        }
    }
    return 0;
}

这个模板代码实现了珂朵莉树的基本操作，包括建树、更新、查询最小值和查询最大值。你可以根据实际需要进行修改和扩展。