题解：P7131 「RdOI R1」变换(turn)

· · 题解

法 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;
}