daily 2

CF 1679C

struct fenwick {
  ll PartialSum[MAXN];
  fenwick() {
    for (int i = 0; i < MAXN; i++) PartialSum[i] = 0;
  }
  inline void add(ll index, ll increase) {
    while (index < MAXN) {
      PartialSum[index] += increase;
      index += index & -index;
    }
  }
  inline ll get(int index) {
    ll sum = 0;
    while (index) {
      sum += PartialSum[index];
      index -= index & -index;
    }
    return sum;
  }
};
void solve() {
  int n, q, op, x, y, xx, yy;
  cin >> n >> q;
  vector<int> r(n + 1), c(n + 1);
  fenwick row, col;
  while (q--) {
    cin >> op;
    switch (op) {
      case 1: {  // put
        cin >> x >> y;
        r[x]++;
        if (r[x] == 1) row.add(x, 1);
        c[y]++;
        if (c[y] == 1) col.add(y, 1);
        break;
      }
      case 2: {
        cin >> x >> y;
        r[x]--;
        if (r[x] == 0) row.add(x, -1);
        c[y]--;
        if (c[y] == 0) col.add(y, -1);
        break;
      }
      case 3: {
        cin >> x >> y;
        cin >> xx >> yy;
        if (xx - x + 1 == row.get(xx) - row.get(x - 1) || // the whole row or column all contains rook
            yy - y + 1 == col.get(yy) - col.get(y - 1)) {
          cout << "YES" << '\n';
        } else {
          cout << "NO" << '\n';
        }
        break;
      }
      default:
        break;
    }
  }
  return;
}

CF 301D

struct fenwick {
  ll PartialSum[MAXN];
  fenwick() {
    for (int i = 0; i < MAXN; i++) PartialSum[i] = 0;
  }
  inline void add(ll index, ll increase) {
    while (index < MAXN) {
      PartialSum[index] += increase;
      index += index & -index;
    }
  }
  inline ll get(int index) {
    ll sum = 0;
    while (index) {
      sum += PartialSum[index];
      index -= index & -index;
    }
    return sum;
  }
};
void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> p(n + 1), id(n + 1);
  vector<vector<int>> group(n + 1);
  fenwick tr;
  for (int i = 1; i <= n; ++i)  {
    cin >> p[i];
    id[p[i]] = i;
  }
  int x, y;
  for (int i = 1; i <= n; ++i) {
    for (int j = i ; j <= n; j += i) {
      x = id[i], y = id[j];
      if (y > x) {
        swap(x, y);
      }
      group[x].push_back(y);
    }
  }// group[i] stores the actual factor which is less than i
  int l, r;
  vector<vector<pii>> query(n + 1);
  for (int i = 1; i <= m; ++i) {
    cin >> l >> r;
    query[r].push_back({l, i}); // query[i] stores the actual query left ptr and the is of the query
  }
  vector<int> ans(m + 1);
  for (int i = 1; i <= n; ++i) {
    for (int v : group[i]) {
      tr.add(v, 1); // the shit we are adding could be counted as the paris between [1, i]
    }
    for (auto& [l, now] : query[i]) {
      ans[now] = tr.get(i) - tr.get(l - 1); // now we are calculating the pair between [l, i] which is like this
    }
  }
  for (int i = 1; i <= m; ++i) {
    cout << ans[i] << " \n";
  }
  return ;
}