我们以 \(\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;
}
标签:opt,int,题解,sqrt,leq,Train,Maintenance,include,day
From: https://www.cnblogs.com/PlayWithCPP/p/17399250.html