洛谷 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;
}