题意

给定整数 $n, m, V$ ，以及四个整数列 $a_i,b_i,A_i,B_i$ 。其中 $A_i,B_i$ 均为非降序列，且四个序列中除 $B_i$ 外元素的值均不超过 $V$ 。

对于所有 $q\in[1,m]$ ，你需要求出最小的 $k\leq n$ ，使得： $\sum_{i=1}^k\left\lceil\frac{b_i}{A_q}\right\rceil a_i\geq B_q$ 。

若这样的 $k$ 不存在，输出 -1。

$1\leq n,m,V\leq3\times10^5,B_i\leq10^9$ 。

题解

这题知道要整除分块但不知道怎么分。考虑每一对 $a_i,b_i$ 的贡献，分整除分块，然后对于每个 $l,r$ 用树状数组维护差分。复杂度 $\mathcal{O}(m\log V+n\sqrt{V}\log V)$ 。

还有一个做法，直接抄题解吧。考虑当国王攻击力为 $x$ 的时卡牌所能承受的轮数，以及此时的攻击力。

当国王的等级提升时，只需要考虑攻击力增加对于卡牌影响的变化。

总的枚举复杂度为 $\mathcal{O}(V\ln V)$ 。使用树状数组维护卡牌血量为某个区间的时候攻击力之和，在符合条件时，在加上对应区间所承受的攻击力，再与当前等级的国王血量相比较即可。总复杂度为 $\mathcal{O}(V\log^2V)$ 。期望得分 100pts。

代码

1

const int N = 3e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m, V;
	ll a[N], b[N], A[N], B[N];
	ll t[N];
	void Modify (int x, ll val) { for (; x <= V; x += x & -x) t[x] += val; }
	ll Query (int x) { ll ans = 0; for (; x; x -= x & -x) ans += t[x]; return ans; }

	int main () {
		n = Read(), m = Read(), V = Read();
		for (int i = 1; i <= n; i++)
			a[i] = Read(), b[i] = Read();
		for (int i = 1; i <= m; i++) 
			A[i] = Read(), B[i] = Read();
		int now = 0;
		for (int i = 1; i <= n; i++) {
			for (int l = 1, r; l <= b[i]; l = r + 1) {
				r = b[i] / (b[i] / l);
				Modify (l, ((int)ceil(1.0 * b[i] / l)) * a[i]);
				Modify (r, -((int)ceil(1.0 * b[i] / l)) * a[i]);
				Modify (r, ((int)ceil(1.0 * b[i] / r)) * a[i]);
				Modify (r + 1, -((int)ceil(1.0 * b[i] / r)) * a[i]);
			}
			Modify(b[i] + 1, a[i]);
			while (now < m && Query(A[now + 1]) >= B[now + 1]) {
				printf("%d\n", i);
				now++;
			}
		}
		for (; now < m; puts("-1"), now++);
		return 0;
	}
}

int main () {
	freopen("france.in", "r", stdin);
	freopen("france.out", "w", stdout);
	Main::main();
	return 0;
}

2

const int N = 3e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	ll a[N], b[N], V;
	ll t[N];
	void Modify (ll x, ll val) { for (; x <= V; x += x & -x) t[x] += val; }
	ll Query (ll x) { ll ans = 0; for (x = min(x, V); x; x -= x & -x) ans += t[x]; return ans; }

	ll sum, ans;
	ll calc (ll x, ll y) {
		ll lst = 1, sum = 0;
		for (int i = 1; (i - 1) * y < V; ++i) {
			for (; lst * x <= i * y && (lst - 1) * x < V; ++lst) {
				if (lst > i) sum += (lst - i) * (Query(lst * x) - Query(max((i - 1) * y, (lst - 1) * x)));
			}
			if (lst > i) sum += (lst - i) * (Query(i * y) - Query((lst - 1) * x));
		}
		return sum;
	}

	int main () {
		n = Read(), m = Read(), V = Read();
		for (int i = 1; i <= n; i++)
			a[i] = Read(), b[i] = Read();
		for (int i = 1, lst = 0; i <= m; i++) {
			ll A = Read(), B = Read();
			if (lst && lst != A) sum -= calc(lst, A);
			lst = A;
			for (; ans < n && sum < B; ++ans, sum += (b[ans] + A - 1) / A * a[ans], Modify(b[ans], a[ans]));
			printf ("%lld\n", sum < B? -1: ans);
		}
		return 0;
	}
}

int main () {
	freopen("france.in", "r", stdin);
	freopen("france.out", "w", stdout);
	Main::main();
	return 0;
}