当前位置：首页 > news >正文

洛谷 P10516 数据结构 Solution

news 来源：原创 2025/7/22 12:10:32

Description

给定序列 $a=(a_1,a_2,\cdots,a_n)$ 和 $b=(b_1,b_2,\cdots,b_n)$ ，有 $m$ 个操作分三种：

$\operatorname{add}(l,r,k,t)$ ：对每个 $i\in[l,r]$ ，若 $a_i\times b_i\le k$ ，则执行 $a_i\gets a_i+t,b_i\gets b_i+t$ .
$\operatorname{set}(i,x,y)$ ：执行 $a_i\gets x,b_i\gets y$ .
$\operatorname{query}(l,r)$ ：求 $\sum\limits_{i=l}^r a_i+b_i$ .

Limitations

$\le n,m \le 10^5$
$\le a_i,b_i,k,t,x,y \le 10^5$
$2\text{s},512\text{MB}$

Solution

若没有 $\operatorname{add}$ 操作是容易维护的.
对于 $\operatorname{add}$ ，若 $t = 0$ 直接忽略；否则 $t > 0$ ，易得一个数至多连续进行 $\sqrt k$ 次 $\operatorname{add}$ .
由于初始的 $a$ 和 $\operatorname{set}$ 操作至多带来约 $(n + q)$ 个数，故 $\operatorname{add}$ 至多影响 $(n+q)\sqrt k$ 个数.
于是可在线段树上维护 $a_i\times b_i$ 的最小值，若 $k$ 大于最小值则直接返回，否则递归修改.
时间复杂度 $O((n+q)\sqrt k\log n$ ).

Code

$2.63\text{KB},1.39\text{s},17.27\text{MB}\;\texttt{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }struct Node {int l, r;i64 a, b, sum, min;void upd(i64 x, i64 y) { a = x, b = y, sum = x + y, min = x * y; }
};struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<i64>& a, const vector<i64>& b) {const int n = a.size();tr.resize(n << 2);build(0, 0, n - 1, a, b);}inline void pushup(int u) {tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;tr[u].min = min(tr[ls(u)].min, tr[rs(u)].min);}inline void build(int u, int l, int r, const vector<i64>& a, const vector<i64>& b) {tr[u].l = l, tr[u].r = r;if (l == r) return tr[u].upd(a[l], b[l]);const int mid = (l + r) >> 1;build(ls(u), l, mid, a, b);build(rs(u), mid + 1, r, a, b);pushup(u);}inline void update(int u, int l, int r, i64 k, i64 t) {if (tr[u].min > k || t == 0) return;if (tr[u].l == tr[u].r) return tr[u].upd(tr[u].a + t, tr[u].b + t);const int mid = (tr[u].l + tr[u].r) >> 1;if (l <= mid) update(ls(u), l, r, k, t);if (r > mid) update(rs(u), l, r, k, t);pushup(u);}inline void set(int u, int p, i64 s, i64 t) {if (tr[u].l == tr[u].r) return tr[u].upd(s, t);const int mid = (tr[u].l + tr[u].r) >> 1;if (p <= mid) set(ls(u), p, s, t);else set(rs(u), p, s, t);pushup(u);}inline i64 sum(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;const int mid = (tr[u].l + tr[u].r) >> 1;i64 res = 0;if (l <= mid) res += sum(ls(u), l, r);if (r > mid) res += sum(rs(u), l, r);return res;}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;scanf("%d %d", &n, &m);vector<i64> a(n), b(n);for (int i = 0; i < n; i++) scanf("%lld", &a[i]);for (int i = 0; i < n; i++) scanf("%lld", &b[i]);SegTree seg(a, b);for (int i = 0, op; i < m; i++) {scanf("%d", &op);if (op == 1) {int l, r; i64 k, t;scanf("%d %d %lld %lld", &l, &r, &k, &t), l--, r--;seg.update(0, l, r, k, t);}else if (op == 2) {int p; i64 s, t;scanf("%d %lld %lld", &p, &s, &t), p--;seg.set(0, p, s, t);}else {int l, r;scanf("%d %d", &l, &r), l--, r--;printf("%lld\n", seg.sum(0, l, r));}}return 0;
}

Description

Limitations

Solution

Code

相关文章：