Solution

记 \(X_k\) 为 \(\sum_{i=1}^kx_i\)，即序列 \(x\) 的前缀和。

对于每座塔都有满魔力时，可以通过二分 \(C\) 来得到会推平哪个前缀。

对于每座塔在前一秒都没有魔力时，可以通过二分 \(R\) 来得到会推平哪个前缀。

对于每座塔在前 \(k\) 秒都没有魔力，且 \(r_ik\le c_i\) 时，可以也通过二分 \(R\) 来得到会推平哪个前缀。记 \(p=\lceil\frac{h}{k}\rceil\)，对 \(p\) 二分即可。

记 \(f_i=\lceil\frac{c_i}{r_i}\rceil\)。对于经过时间 \(t\)，一座塔 \(i\) 满魔力当且仅当 \(t\ge f_i\)。

如果不考虑 \(r_ik\le c_i\) 的限制：

可以尝试实现一个数据结构，能够支持查询的 \(t\ge f_i\) 塔的魔力总和与 \(t<f_i\) 的塔的恢复速率总和，就可以得到经过时间 \(t\) 后的魔力和。

考虑线段树。

在下标 \(f_i\) 插入每个塔的 \(c_i\) 和 \(r_i\) 并维护 \(c\) 和 \(r\) 的区间和。查询时只需要查询前缀 \([1,t]\)。

问题是现在只支持维护魔力和，并不能算出要推平到哪个前缀。

考虑倍增。

每次判断 \([1, v]\) 的塔的前缀魔力和是否大于 \(h\)，大于就不跳，小于等于就跳。倍增要注意可能 \([1,1]\) 就大于 \(h\)，不过这些都是基本的实现细节。

问题是线段树一下就插入了 \(n\) 个塔的信息，区分不了前 \(v\) 座塔魔力和 和 后 \(n-v\) 座塔的魔力和。

考虑主席树。

按 \(1\sim n\) 的顺序依次在下标 \(f_i\) 插入 \(c_i,r_i\)，对于查询区间 \([l,r]\)，直接用版本 \(r\) 减去版本 \(l-1\)。注意到我们维护的信息是 \(c\) 和 \(r\) 的区间和，具有可减性，可以直接维护。

通过主席树和倍增，我们可以做到在 \(\mathcal O(\log^2 n)\) 的时间复杂度内查询推平哪个前缀。

仍有一个问题，实现上述做法后，我们能回答的问题都有一个限制：每座塔需要都在同一秒没有魔力。

显然实际上很难出现这样的情况。

不过刚才反复出现了推平二字……

考虑珂朵莉树。

我们用珂朵莉树维护若干个区间 \([l,r,t]\)，表示区间 \([l,r]\) 的每座塔都在 \(t\) 时刻被榨干。对于在 \(t\) 时刻没有完全榨干的塔，给它打个标记，分配一个 \([i,i,-t]\) 的线段（显然正常的 \(t\) 不会是负数，标记不会混淆）。

不过珂朵莉树的最大问题在于时间复杂度。

发现每次操作，我们会抹平一段前缀，并新建两个线段 \([1, p, t]\) 和 \([p,p,-t]\)，总线段数是 \(\mathcal O(q)\) 的。而每个线段最多被插入一次，删除一次，对时间复杂度的总贡献是 \(\mathcal O(1)\) 的，珂朵莉树的总时间复杂度是 \(\mathcal O(q\log q)\) 的（用 map 或 set 实现自带 \(\log\)）。而先前使用的主席树也可以支持查询的任意一个线段 \([l,r]\) 内的塔。

总时间复杂度 \(\mathcal O(q(\log^2 n+\log q))\)。

Code

// Problem: F. Tower Defense
// From: Codeforces - Educational Codeforces Round 124 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1651/problem/F
// Time: 2022-03-15 16:54
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 2e5+10, mxd = 1e7;

int n, c[mxn], r[mxn], tt, root[mxn], lst[mxn], lg[mxn];
LL ans;
struct node {
	LL sc, sr; inline node operator + (const node& rhs) const { return {sc + rhs.sc, sr + rhs.sr}; }
} nd[mxd];
int lc[mxd], rc[mxd], tot;
#define mid ((L+R)>>1)
inline void psup(int o) { nd[o] = nd[lc[o]] + nd[rc[o]]; }
void insert(int& o, int rt, int p, node x, int L = 1, int R = mxn) {
	if(!o) o = ++tot; if(L == R) return nd[o] = nd[rt] + x, void();
	if(p <= mid) insert(lc[o], lc[rt], p, x, L, mid), rc[o] = rc[rt];
	else insert(rc[o], rc[rt], p, x, mid+1, R), lc[o] = lc[rt];
	psup(o);
}
node query(int r, int l, int p, int L = 1, int R = mxn) {
	// 计算版本r-l的小于等于 p 的 sc 和大于 p 的sr
	if(R <= p) return {nd[r].sc-nd[l].sc, 0}; if(L > p) return {0, nd[r].sr-nd[l].sr};
	return query(lc[r], lc[l], p, L, mid) + query(rc[r], rc[l], p, mid+1, R);
}
map <int, int> mp;
inline void cut(int p) {
	if(mp.find(p) == mp.end()) mp[p] = prev(mp.lower_bound(p))->second;
}
inline LL get(int l, int r, int dt) {
	node s = query(root[r], root[l-1], dt);
	return s.sc + (s.sr*dt);
}
// node[P] 时间为 P 的时候满魔力的塔的信息

signed main() {
	scanf("%d", &n); lg[0] = -1;
	for(int i = 1; i <= n; ++i) scanf("%d%d", c+i, r+i), lg[i] = lg[i>>1] + 1;
	for(int i = 1; i <= n; ++i) insert(root[i], root[i-1], min((c[i]+r[i]-1)/r[i], mxn), {c[i], r[i]});
	mp[n+1] = 114514; mp[1] = -1919810;
	scanf("%d", &tt);
	while(tt--) {
		int t, L, R, dt, pos; LL h, dec; scanf("%d%lld", &t, &h);
		++t;	// 存在 t = 0, 建议先 +1 以保证特殊标记可以区分开
		auto it = mp.begin();
		while(it->first != n+1) {
			if(it -> second < 0 && it -> second != -1919810) {
				// 这个点删了，但没完全删
				dt = t + it->second, pos = it -> first;
				dec = min((LL)c[pos], lst[pos] + (LL)r[pos] * dt);
				if(h >= dec) { h -= dec; it = mp.erase(it); }
				else { lst[pos] = dec - h; it -> second = -t; h = 0; break; }
			} else {
				L = it->first, R = next(it)->first - 1, dt = t - it->second;
				dec = get(L, R, dt);
				if(h >= dec) { h -= dec; it = mp.erase(it); }
				else {
					for(int d = lg[R-L+1], v; v = L + (1<<d), ~d; --d) if(v <= R) {
						// 判断 [L, v] 的和是否比 h 大，大了不跳，小了就跳
						dec = get(L, v, dt);
						if(h >= dec) h -= dec, L = v + 1;
					}
					if((dec = get(L, L, dt)) <= h) h -= dec, ++L;
					// 此时 get(L, L, dt) > h
					dec = min((LL)c[L], (LL)r[L] * dt);
					dec -= h; lst[L] = dec; h = 0; cut(L), cut(L+1);
					mp.erase(it); mp[L] = -t; break;
				}
			}
		}
		if(mp.find(1) == mp.end()) mp[1] = t; ans += h;
	}
	printf("%lld\n", ans);
	return 0;
}