自动搬运

查看原文

来自洛谷，原作者为

	weilycoder Per Aspera Ad Astra

搬运于2025-08-24 22:26:55，当前版本为作者最后更新于2024-09-26 18:11:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

法 1

题目要求的实际上就是这样的函数的复合：

$$\begin{aligned} f(x)&=\left\lfloor\dfrac{x}{p}\right\rfloor+q \\ &=\left\lfloor\dfrac{x+pq}{p}\right\rfloor \end{aligned} $$

所以我们求一下 $f_2(f_1(x))$ 看看啥样：

$$\begin{aligned} f_2(f_1(x))&=\left\lfloor\dfrac{\left\lfloor\frac{x+p_1q_1}{p_1}\right\rfloor+p_2q_2}{p_2}\right\rfloor \\ &=\left\lfloor\dfrac{x+p_1q_1+p_1p_2q_2}{p_1p_2}\right\rfloor \end{aligned} $$

注意到函数始终是 $\left\lfloor\frac{x+C}{a}\right\rfloor$ 的形式，我们考虑线段树维护。

但是由于复合后的 $a$ 和 $C$ 要做乘法，数大的时候会炸掉，考虑用 long double 乱搞一下。

我们把函数写成 $f(x)=\left\lfloor\frac{x}{a}+b\right\rfloor$ 的形式，这里 $a,b$ 均为实数，复合的形式是

$$f_2(f_1(x))=\left\lfloor\dfrac{\left\lfloor\frac{x}{a_1}+b_1\right\rfloor}{a_2}+b_2\right\rfloor=\left\lfloor\dfrac{x}{a_1a_2}+\left(\dfrac{b_1}{a_2}+b_2\right)\right\rfloor $$

上线段树即可。

法 2

观察一下 $f(x)=\left\lfloor\frac{x+c}{a}\right\rfloor$，不妨改成 $f(x)=\left\lfloor\frac{x+c}{a}\right\rfloor+b$ 的形式，其中 $0\le c<a$。

由于 $0\le x\le 10^6$，我们讨论 $a$ 是否大于 $10^6$。

若 $a\le 10^6$，暴力维护。

若 $a\gt 10^6$，由于 $x\le 10^6$，原函数就是

$$f(x)=\begin{cases} b&,x>a-c \\ b+1&,\text{otherwise} \end{cases} $$

这个玩意不好和其他函数复合，不妨把它写成

$$f(x)=\left\lfloor\dfrac{x+\max(10^6+1-(a-c),0)}{10^6+1}\right\rfloor+b $$

容易证明在 $x\le 10^6$ 时两个函数是同一函数。

上线段树维护。

Code

这是方法 1 的代码，被 Hack 了叫我一声，有 dalao 证明正确了也叫我一声。

#include <cmath>
#include <iostream>
using namespace std;

const int N = 1e5 + 7;
int n, m, P[N], Q[N];
struct node_t {
  long double a, b;
  inline node_t operator*(const node_t &g) const {
    return {a * g.a, g.b / a + b};
  }
  inline int64_t operator()(int x) const { return floorl(x / a + b); }
} tree[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
void build(int p, int l, int r) {
  if (l == r) {
    tree[p] = {(long double)P[l], (long double)Q[l]};
    return;
  }
  int mid = ((r - l) >> 1) + l;
  build(lc, l, mid), build(rc, mid + 1, r);
  tree[p] = tree[rc] * tree[lc];
}
void update(int p, int l, int r, int x, int a, int b) {
  if (l == r) {
    tree[p] = {(long double)a, (long double)b};
    return;
  }
  int mid = ((r - l) >> 1) + l;
  if (x <= mid)
    update(lc, l, mid, x, a, b);
  else
    update(rc, mid + 1, r, x, a, b);
  tree[p] = tree[rc] * tree[lc];
}
node_t ask(int p, int l, int r, int s, int t) {
  if (s <= l && r <= t)
    return tree[p];
  int mid = ((r - l) >> 1) + l;
  node_t res{(long double)1, (long double)0};
  if (s <= mid)
    res = ask(lc, l, mid, s, t) * res;
  if (t > mid)
    res = ask(rc, mid + 1, r, s, t) * res;
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    cin >> P[i];
  for (int i = 1; i <= n; ++i)
    cin >> Q[i];
  build(1, 1, n);
  while (m--) {
    char op;
    cin >> op;
    switch (op) {
    case 'm': {
      int i, p, q;
      cin >> i >> p >> q;
      update(1, 1, n, i, p, q);
      break;
    }
    case 'q': {
      int x, s, t;
      cin >> x >> s >> t;
      cout << ask(1, 1, n, s, t)(x) << '\n';
    }
    }
  }
  return 0;
}