【友谊就是魔法！！】CF453E

Friendship is magic！！

前置简单题： [ABC255Ex] Range Harvest Query。

考虑维护 \(t\) 相同的颜色段。

然后注意到一个颜色段被取出后必然被推平，所以一个段只会被遍历一次。

一次只会增加一个颜色段，可以 \(O(q \log n)\) 来维护。

然后我们考虑对于没有推平过和推平过的分类：

• 没有推平过：

考虑计算 \(s_i + t \times r_i < m_i\) 的左式总和，然后再计算 \(s_i + t \times r_i > m_i\) 的右式总和。

可以考虑的办法是对于左边大于右边的阈值 \(t_i\) 上二位数点，然后再结合前缀和计算。

具体来说是维护 \(t_i \leq t\) 的所有 \(m_i\) 以及 \(t_i > t\) 的所有 \(s_i\) 和 \(r_i\)，然后就可以分类计算贡献。

• 推平过：
  即原来的 \(s_i \to 0\) 的情况。

不难用两个主席树维护。复杂度 \(O((n + q) \log n)\)。

代码很丑。

// LUOGU_RID: 139435454
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)

using namespace std;
bool s1;

typedef long long ll;
const int _ = 1e5 + 5, lim = 1e5 + 5, mod = 998244353;
int power (int x, int y) {
	int ret = 1;
	for ( ; y; y >>= 1, x = 1ll * x * x % mod)
		if (y & 1) ret = 1ll * ret * x % mod;
	return ret;
}

struct node {
	int l, r, t;
	node (int _l = -1, int _r = -1, int _t = -1) {
		l = _l, r = _r, t = _t;
	}
	bool operator < (const node & x) const { return l < x.l; }
};
set <node> s;
auto split (int x) {
	auto it = s.lower_bound(node(x));
	if (it != s.end() && it -> l == x) return it;
	-- it;
	node tmp(*it);
	s.erase(tmp), s.insert(node(tmp.l, x - 1, tmp.t));
	return s.insert(node(x, tmp.r, tmp.t)).first;
}

int tot[2], rt[_], rtp[_];
namespace dataStructure {
	struct Info { 
		ll sums = 0, suma = 0, sumr = 0;
	} initp;
	Info operator + (Info x, Info y) { return {x.sums + y.sums, x.suma + y.suma, x.sumr + y.sumr}; }
	Info operator - (Info x, Info y) { return {x.sums - y.sums, x.suma - y.suma, x.sumr - y.sumr}; }
	struct SegMent {
		int op;
		int lc[_ * 20], rc[_ * 20];
		Info t[_ * 20];
		void ins (int &x, int p, int l, int r, int v, Info k) {
			x = ++ tot[op], lc[x] = lc[p], rc[x] = rc[p], t[x] = t[p] + k;
			if (l == r) return ;
			int mid = (l + r) >> 1;
			v <= mid ? ins(lc[x], lc[p], l, mid, v, k) : ins(rc[x], rc[p], mid + 1, r, v, k);
		}
		Info query (int x, int l, int r, int ql, int qr) {
			if (!x) return initp;
			if (ql <= l && r <= qr) return t[x];
			int mid = (l + r) >> 1;
			Info ret = initp;
			if (ql <= mid) ret = ret + query(lc[x], l, mid, ql, qr);
			if (qr > mid) ret = ret + query(rc[x], mid + 1, r, ql, qr);
			return ret;
		}
	} t1, t2;
	
} using namespace dataStructure;
int n, q;
int a[_], m[_], r[_];
ll suma[_], sumr[_];

bool s2;
int main () {
	cin >> n;
	t1.op = 0, t2.op = 1;
	rep(i, 1, n) {
		scanf("%d%d%d", & a[i], & m[i], & r[i]);
		
		if (r[i]) {
			int t = (m[i] - a[i]) / r[i];
			if (t * r[i] + a[i] < m[i]) 
				t1.ins(rt[i], rt[i - 1], 0, lim, t + 1, {m[i], a[i], r[i]});
			else 
				t1.ins(rt[i], rt[i - 1], 0, lim, t, {m[i], a[i], r[i]});			
		} else t1.ins(rt[i], rt[i - 1], 0, lim, 0, {a[i], a[i], 0});
		
		sumr[i] = sumr[i - 1] + r[i], suma[i] = suma[i - 1] + a[i];
		
		if (r[i]) {
			int t = m[i] / r[i];
			if (t * r[i] < m[i]) 
				t2.ins(rtp[i], rtp[i - 1], 0, lim, t + 1, {m[i], 0, r[i]});
			else 
				t2.ins(rtp[i], rtp[i - 1], 0, lim, t, {m[i], 0, r[i]});			
		} else t2.ins(rtp[i], rtp[i - 1], 0, lim, 0, {0, 0, 0});
		
	}
	s.insert(node(1, n, 0));
	cin >> q;
	while (q --) {
		int l, r, t;
		ll ret = 0;
		scanf("%d%d%d", & t, & l, & r);
		auto itr = split(r + 1), itl = split(l);
		for (auto it = itl; it != itr; it ++) {
			int l = it -> l, r = it -> r, c = it -> t;
			if (!c) {
				c = t;
				Info res = t1.query(rt[r], 0, lim, 0, c) - t1.query(rt[l - 1], 0, lim, 0, c);
				ret += res.sums;
				ret += 1ll * c * (sumr[r] - sumr[l - 1] - res.sumr);
				ret += (suma[r] - suma[l - 1] - res.suma);
			} else {
				c = min(lim, t - c);
				Info res = t2.query(rtp[r], 0, lim, 0, c) - t2.query(rtp[l - 1], 0, lim, 0, c);
				ret += res.sums;
				ret += 1ll * c * (sumr[r] - sumr[l - 1] - res.sumr);
			}
		}
		s.erase(itl, itr), s.insert(node(l, r, t));
		printf("%lld\n", ret);
	}
	return 0;
}