CF 1581 E. Train Maintenance(根号分治)

题意：总共有$n$个机器，$m$天，每天有一个机器开始工作或者停止工作，当其从开始工作的那天开始算起，连续工作$x_i$天，然后维修$y_i$天，一直轮流直到$m$天结束。求对于$m$天中的每一天，求当前有多少个机器正在进行维修。
分析：$x_i$和$y_i$轮流进行可以想到进行取模，而总天数又是$m$，因此可以进行根号分治。对于$x_i + y_i \gt sqrt(m)$的情况，进行暴力处理，即从$s$天开始，第$s + x_i$到$s + x_i + y_i$天都增加$1$，这里由于是正序枚举$m$，可以在线维护一个差分数组$d$，然后维护$d$的前缀和$sum$；对于$x_i + y_i \leq sqrt(m)$的情况，维护一个$cnt(len,mod)$表示$s$在长度为$len$的段中模$s$为$mod$的贡献，这样总的复杂度就均摊为$m \times sqrt(m)$。

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  constexpr int sqn = 256;
  int n, m;
  cin >> n >> m;
  vector<int> x(n + 1), y(n + 1), lst(m + 1), d(m + 1); 
  vector<vector<int> > cnt(sqn + 1, vector<int>(sqn + 1));
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  function<void(int,int,int)> modify = [&](int s, int k, int v) {
    int len = x[k] + y[k];
    int l = (s + x[k]) % len, r = (s - 1) % len;
    if (l <= r) for (int i = l; i <= r; i++) cnt[len][i] += v ;
    else {
      for (int i = 0; i <= r; i++) cnt[len][i] += v;
      for (int i = l; i < len; i++) cnt[len][i] += v;
    }
  };
  function<int(int)> query = [&](int s) {
    int ret = 0;
    for (int i = 2; i <= sqn; i++) ret += cnt[i][s % i];
    return ret;
  };
  int sum = 0; // sum即为差分数组的前缀和 
  for (int it = 1; it <= m; it++) {
    int op, k;
    cin >> op >> k;
    if (op == 1) {
      if (x[k] + y[k] > sqn) {
        for (int i = it + x[k]; i <= m; i += x[k] + y[k]) {
          d[i] ++ ;
          if (i + y[k] <= m) d[i + y[k]] -- ;
        }
      } else {
        modify(it, k, 1);
      }
      lst[k] = it;
    } else {
      if (x[k] + y[k] > sqn) {
        for (int i = lst[k] + x[k]; i <= m; i += x[k] + y[k]) {
          d[i] -- ;
          if (i + y[k] <= m) d[i + y[k]] ++ ;
          if (i < it && i + y[k] >= it) sum -- ;
          // 这里即去掉在it前对差分数组d++的那些贡献 
        }
      } else {
        modify(lst[k], k, -1);
      }
    }
    sum += d[it];
    cout << sum + query(it) << '\n';
  }
  return 0;
}