题解 | 小红的数组操作

小红的数组操作

https://ac.nowcoder.com/acm/contest/88888/F

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;
}
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务