CF1580C Train Maintenance题解

SunnyYuan的博客 / 2023-05-14 / 原文

我们以 \(\sqrt m\) 为分界点来进行平衡。

设当前在进行第 \(k\) 次操作，询问 \(i\)。

对于 \(x_i + y_i \leq \sqrt m\)，可以在 \(last_{x_i + y_i,day \bmod (x_i + y_i)}\) 上 \(+1\)，其中 \(day\) 表示维修的时间，\(k + x_i \leq day \leq k + x_i + y_i - 1\)，输出时暴力统计即可。

对于 \(x_i + y_i > \sqrt m\) 的，可以在利用差分数组在 \(f_{day_1}\) 上 \(+ 1\)，在 \(f_{day_2}\) 上 \(-1\)，其中 \(day_1\) 表示所有的维修时间的开始时间，\(day_2\) 表示所有维修时间的结束时间的后面一天。

时间复杂度：\(O(m\sqrt m)\)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, V = 450;

int n, m, s;
int st[N];
int f[N];
int last[V][V];
int x[N], y[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	s = sqrt(m);
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	int opt, a;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		cin >> opt >> a;
		if (opt == 1) {
			if (x[a] + y[a] > s) {
				for (int j = i + x[a]; j <= m; j += x[a] + y[a]) {
					f[j] += 1;
					if (j + y[a] <= m) f[j + y[a]] -= 1;
				}
			}
			else {
				int b = i + x[a], e = i + x[a] + y[a] - 1;
				for (int j = b; j <= e; j++) {
					last[x[a] + y[a]][j % (x[a] + y[a])]++;
				}
			}
			st[a] = i;
		}
		else {
			if (x[a] + y[a] > s) {
				for (int j = st[a] + x[a]; j <= m; j += x[a] + y[a]) {
					f[j] -= 1;
					if (j < i) sum--;
					if (j + y[a] <= m) {
					    f[j + y[a]] += 1;
					    if (j + y[a] < i) sum++;
					}
				}
			}
			else {
				for (int j = st[a] + x[a]; j < st[a] + x[a] + y[a]; j++) {
					last[x[a] + y[a]][j % (x[a] + y[a])]--;
				}
			}
		}
		sum += f[i];
		int res = sum;
		for (int j = 1; j <= s; j++) res += last[j][i % j];
		cout << res << '\n';
	}
	return 0;
}