题解 | 小红的数组操作

F n+1颗线段树写法供参考

每个数组用一颗线段树维护min，再另开一颗线段树维护前i个数组的min

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define lowbit(x) x & (-x)

const int N = 1e5 + 10, M = 1010, mod = 998244353, inf = 2e9;
const double eps = 1e-9;
typedef pair<int, int> pt;
typedef long long ll;
typedef unsigned long long ull;
 
void pushup(vector<int> &tr, int p) {
    tr[p] = min(tr[p * 2], tr[p * 2 + 1]);
}

void build(vector<int> &tr, int p, int l, int r, vector<int> &a) {
    if (l == r) {
        tr[p] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(tr, p * 2, l, mid, a);
    build(tr, p * 2 + 1, mid + 1, r, a);
    pushup(tr, p);
}

void modify(vector<int> &tr, int p, int l, int r, int x, int v) {
    if (l == r) {
        tr[p] = v;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) modify(tr, p * 2, l, mid, x, v);
    else modify(tr, p * 2 + 1, mid + 1, r, x, v);
    pushup(tr, p);
}

int query(vector<int> &tr, int p, int l, int r, int x, int y) {
    if (l > y || r < x) {
        return (int)2e9;
    }
    if (l >= x && r <= y) {
        return tr[p];
    }
    int mid = l + r >> 1;
    return min(query(tr, p * 2, l, mid, x, y), query(tr, p * 2 + 1, mid + 1, r, x, y));
    pushup(tr, p);
}
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n + 1);
    vector<vector<int>> tr(n + 1);
    vector<int> sz(n + 1);
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        a[i].resize(m + 1);
        tr[i].resize((m + 1) * 4);
        sz[i] = m;
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        build(tr[i], 1, 1, m, a[i]);
    }

    int q;
    cin >> q;
    vector<int> pre((n + 1) * 4, 2e9);
    for (int i = 1; i <= n; i++) {
        modify(pre, 1, 1, n, i, tr[i][1]);
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, j, x;
            cin >> i >> j >> x;
            modify(tr[i], 1, 1, sz[i], j, x);
            modify(pre, 1, 1, n, i, tr[i][1]);
        }
        else {
            int i;
            cin >> i;
            cout << query(pre, 1, 1, n, 1, i) << endl;
        }
    }
}
signed main() {
    //freopen("title.in", "r", stdin);
    //freopen("std.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}