洛谷 P10516 数据结构 Solution

Description

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

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

Limitations

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

Solution

若没有 $\mathrm{add}$ 操作是容易维护的.
对于 $\mathrm{add}$，若 $t=0$ 直接忽略；否则 $t>0$，易得一个数至多连续进行 $\sqrt{k}$ 次 $\mathrm{add}$.
由于初始的 $a$ 和 $\mathrm{set}$ 操作至多带来约 $(n+q)$ 个数，故 $\mathrm{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}\text{(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;
}