BJOI 2019 简要题解

2020-04-24

~~听说大赏的意思好像和我之前认为的不太一样?~~

没文化啊.png

「BJOI2019」奥术神杖

~~为什么剧情里总是向过往寻求力量呢 (~~

题目链接

https://loj.ac/problem/3089

解题思路

~~1 月份做过结果忘地一干二净~~

设选择后神杖上的宝石后, 得出的生效的咒语序列为 $a_i$. 如果答案比 $x$ 优, 那么有

$\left( \prod_{i = 1} ^ c V_{a_i} \right) ^ {1 / c} > x$

运用一些运算的技巧, 有

$\ln \left( \sum_{i = 1} ^ c V_{a_i} \right) > c \ln x$ $\ln \left( \sum_{i = 1} ^ c (V_{a_i} - c \ln x)\right) > 0$

0-1 分数规划即可. 现在的重点在于计算中间和式的最大值.

考虑在 AC 自动机上 DP. 设 $f(i, u)$ 表示匹配到 $T$ 中第 $i$ 个位置, 以及 AC 自动机上第 $u$ 个节点在最大值.

那么根据 $T_i$ 处的字符转移即可, 输出方案可在 DP 时记录每次转移的选择就好了. 注意在处理权值时, 需要将 $u$ 的权值加到 $\operatorname{fail}(u)$ 上, 以及不要忽略多个串在同一节点上的情况.

记字符集大小为 $c$, 那么时间复杂度为 $O(nsc\log V)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3089
// DeP
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

template<typename T> inline bool ckmax(T& a, const T& b) {
  return (a < b)? (a = b, true): false;
}

const int MAXN = 15e2 + 5, SIGMA = 10;
const double EPS = 1e-9, INFD = 1e9 * MAXN;

inline int dcmp(const double& p) {
  return (fabs(p) < EPS)? 0: (p < 0? -1: 1);
}

int n, m;
char T[MAXN], S[MAXN];

double f[MAXN][MAXN];
int g[MAXN][MAXN][2];

namespace AC {
  int ch[MAXN][SIGMA], fail[MAXN], size[MAXN], nidx;
  double A[MAXN], val[MAXN];

  inline void init() { nidx = 1; }

  inline void insert(const double& w) {
    int u = 1, lgt = strlen(S + 1);
    for (int i = 1; i <= lgt; ++i) {
      int c = S[i] - '0';
      if (!ch[u][c]) ch[u][c] = ++nidx;
      u = ch[u][c];
    }
    val[u] += w, ++size[u];
  }

  void getfail() {
    static int Q[MAXN], head, tail;
    Q[head = 1] = tail = 0, fail[1] = 1;
    for (int c = 0; c < SIGMA; ++c) {
      int& v = ch[1][c];
      if (v) Q[++tail] = v, fail[v] = 1; else v = 1;
    }
    while (head <= tail) {
      int u = Q[head++];
      size[u] += size[fail[u]], val[u] += val[fail[u]];
      for (int c = 0; c < SIGMA; ++c) {
        int& v = ch[u][c];
        if (v) Q[++tail] = v, fail[v] = ch[fail[u]][c];
        else v = ch[fail[u]][c];
      }
    }
  }

  bool check(const double& Mid, bool flag = false) {
    for (int u = 1; u <= nidx; ++u)
      A[u] = val[u] - Mid * size[u];
    for (int i = 0; i <= n; ++i)
      for (int u = 1; u <= nidx; ++u) f[i][u] = -INFD;

    f[0][1] = 0;
    for (int i = 1; i <= n; ++i)
      for (int u = 1; u <= nidx; ++u) if (f[i - 1][u] > -INFD) {
        if (T[i] == '.') {
          for (int c = 0; c < SIGMA; ++c) {
            const int& v = ch[u][c];
            if (ckmax(f[i][v], f[i - 1][u] + A[v]))
              g[i][v][0] = c, g[i][v][1] = u;
          }
        } else {
          const int c = T[i] - '0', &v = ch[u][c];
          if (ckmax(f[i][v], f[i - 1][u] + A[v]))
            g[i][v][0] = c, g[i][v][1] = u;
        }
      }

    int v = 1;
    for (int u = 2; u <= nidx; ++u)
      if (f[n][u] > f[n][v]) v = u;
    if (flag)
      for (int u = v, i = n; i; --i)
        S[i] = g[i][u][0] + '0', u = g[i][u][1];
    return dcmp(f[n][v]) > 0;
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  AC::init();
  
  scanf("%d%d%s", &n, &m, T + 1);
  for (int w, i = 1; i <= m; ++i)
    scanf("%s%d", S + 1, &w), AC::insert(log(w));
 
  AC::getfail();
  double L = 0.0, R = log(INFD);
  while (dcmp(R - L) > 0) {
    double Mid = (L + R) / 2.0;
    if (AC::check(Mid)) L = Mid; else R = Mid;
  }

  AC::check(L, true), puts(S + 1);
  return 0;
}

「BJOI2019」勘破神机

题目链接

https://loj.ac/problem/3090

解题思路

先假设我们已经知道了第 $n$ 项的答案为 $h_n$. 那么所求即为 $\frac{1}{R - L + 1}$ 乘上

$\sum_{n = L} ^ R H(n, k) = \sum_{n = L} ^ R \binom{h_n}{k} = \frac{1}{k!} \sum_{n = L} ^ R {h_n} ^ {\underline k}$

后者是下降幂的形式, 可以联想到

$x ^ {\underline{k}} = \sum_{i = 0} ^ k (-1) ^ {k - i} \begin{bmatrix} k \\ i \end{bmatrix} x ^ i$

其中 $\begin{bmatrix} n \ m \end{bmatrix}$ 表示第一类 Stirling 数. 此处可直接使用有符号第一类 Stirling 数来消去 $-1$.

那么原式可化作

这就启发我们去求 $h_n$ 的通项公式.

先考虑 $m = 2$ 的情况, 此时是个经典问题. 记 Fibonacci 数列为 $f_n$, 且有 $f_0 = 0, f_1 = 1$, 那么 $f_{n + 1}$ 即为 $2 \times n$ 网格的填充方案, 此时直接将 $L, R + 1$.

根据 Fibonacci 数列的递推公式, 并利用特征方程可以解出 $f_n$ 的通项为

$f_n = \frac{1}{\sqrt 5} \left( \frac{1 + \sqrt 5}{2} \right) ^ n - \frac{1}{\sqrt 5} \left( \frac{1 - \sqrt 5}{2} \right) ^ n$

设 $A = \frac{1}{\sqrt 5}, B = -\frac{1}{\sqrt 5}, x = \frac{1 + \sqrt 5}{2}, y = \frac{1 - \sqrt 5}{2}$, 那么 $f_n = A x ^ n + B y ^ n$.

带入到原式继续化简, 可得

$\frac{1}{k!} \sum_{n = L} ^ R \sum_{i = 0} ^ k (-1) ^ {k - i} \begin{bmatrix} k \\ i \end{bmatrix} {h_n} ^ i = \frac{1}{k!} \sum_{i = 0} ^ k (-1) ^ {k - i} \begin{bmatrix} k \\ i \end{bmatrix} \sum_{n = L} ^ R (A x ^ n + B y ^ n) ^ i$ $\frac{1}{k!} \sum_{i = 0} ^ k (-1) ^ {k - i} \begin{bmatrix} k \\ i \end{bmatrix} \sum_{n = L} ^ R \sum_{j = 0} ^ i \binom{i}{j} A^i B^{i - j} (x^j y^{i - j}) ^ n$ $\frac{1}{k!} \sum_{i = 0} ^ k (-1) ^ {k - i} \begin{bmatrix} k \\ i \end{bmatrix} \sum_{j = 0} ^ i \binom{i}{j} A^i B^{i - j} \sum_{n = L} ^ R (x^j y^{i - j}) ^ n$

后者为等比数列部分和, 直接计算 $O(\log R)$ 即可. 时间复杂度 $O(k ^ 2 \log R)$.

此时还有一个问题. 注意到 $5 ^ {(998244353 - 1) / 2} \equiv -1 \pmod {998244353}$, 即模意义下 $\sqrt{5}$ 不存在. 此时可运用称之为 “扩域” 的技巧, 也就是将数表示为 $x + \sqrt 5 y$ 的形式, 用类似于模意义下复数的方式进行运算. 同时, 最终结果一定为整数, 取 $x$ 值即可.

现在考虑 $m = 3$ 的情况.

手玩之后可以得出, 除去 $n = 2$ 的情况之外, 仅存在两种方式, 使得长度为偶数的网格被铺满, 且不是若干长度较小的偶数网格拼接而成. 同时, $n$ 为奇数时方案数为 $0$.

设 $g_n$ 为铺满 $3 \times 2n$ 网格的方案数. 则根据上述性质, 有

$g_n = \begin{cases} 0 & n = 0 \\ 3 & n = 1 \\ g_{n - 1} + 2 \sum\limits_{i = 1} ^ n g_{n - i} & n > 1\end{cases}$

利用一些运算的技巧, 可得

$g_n = 4 g_{n - 1} - g_{n - 2}$

利用之前的方法, 可以得出

$g_n = \left( \frac{3 + \sqrt{3}}{6} \right) (2 + \sqrt{3}) ^ n + \left( \frac{3 - \sqrt{3}}{6} \right) (2 - \sqrt{3}) ^ n$

直接算就完事了.

时间复杂度 $O(k ^ 2 \log R)$. ~~然而存在时间复杂度更为优秀的神仙做法…~~

代码实现

在利用快速幂计算 $x + \sqrt{5} y$ 的幂时, 不要天真地把指数模 $P - 1$…

> 点击显示 / 隐藏

// LOJ #3090
// DeP
#include <cstdio>
#include <cassert>
using namespace std;

typedef long long LL;
const int MAXK = 5e2 + 5, P = 998244353;

inline int Mod(const int& x) { return x + (x >> 31 & P); }
inline int mns(const int& a, const int& b) { return Mod(a - b); }
inline int pls(const int& a, const int& b) { return Mod(a + b - P); }
inline int mul(const int& a, const int& b) { return 1LL * a * b % P; }

int stl[MAXK][MAXK];
int fac[MAXK], ifac[MAXK], inv[MAXK];

inline int C(int n, int m) {
  return (n < m)? 0: mul(mul(fac[n], ifac[m]), ifac[n - m]);
}

int fpow(int base, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) ret = mul(ret, base);
    base = mul(base, base), b >>= 1;
  }
  return ret;
}

void PreDone(int N) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= N; ++i)
    inv[i] = mul(inv[P % i], P - P / i);
  ifac[0] = fac[0] = 1;
  for (int i = 1; i <= N; ++i)
    fac[i] = mul(i, fac[i - 1]), ifac[i] = mul(inv[i], ifac[i - 1]);
  stl[1][1] = 1;
  for (int i = 2; i <= N; ++i)
    for (int j = 1; j <= i; ++j)
      stl[i][j] = mns(stl[i - 1][j - 1], mul(i - 1, stl[i - 1][j]));
}

LL Sqrt;

struct Int {
  int x, y; // x + sqrt{Sqrt} y
  Int (int _x = 0, int _y = 0): x(_x), y(_y) { }
  Int operator + (const Int& rhs) const {
    return Int(pls(x, rhs.x), pls(y, rhs.y));
  }
  Int operator - (const Int& rhs) const {
    return Int(mns(x, rhs.x), mns(y, rhs.y));
  }
  Int operator * (const Int& rhs) const {
    int ac = mul(x, rhs.x), ad = mul(x, rhs.y), bc = mul(y, rhs.x);
    return Int(pls(ac, Sqrt * y % P * rhs.y % P), pls(bc, ad));
  }
  Int operator / (const Int& rhs) const {
    int ac = mul(x, rhs.x), ad = mul(x, rhs.y), bc = mul(y, rhs.x);
    int iv = fpow(mns(mul(rhs.x, rhs.x), Sqrt * rhs.y % P * rhs.y % P), P - 2);
    return Int(mns(ac, Sqrt * y % P * rhs.y % P), mns(bc, ad)) * iv;
  }
  Int operator += (const Int& rhs) { return x = pls(x, rhs.x), y = pls(y, rhs.y), *this; }
  Int operator -= (const Int& rhs) { return x = mns(x, rhs.x), y = pls(y, rhs.y), *this; }
  Int operator *= (const Int& rhs) { return *this = *this * rhs; }
};

inline Int conj(const Int& x) { return Int(x.x, mns(0, x.y)); }

Int fpowInt(Int base, LL b) {
  Int ret = Int(1, 0);
  for ( ; b > 0; base *= base, b >>= 1)
    if (b & 1) ret *= base;
  return ret;
}

inline Int Sum(const LL& L, const LL& R, const Int& q) {
  if (q.x == 1 && q.y == 0) return (R - L + 1) % P;
  return (fpowInt(q, R + 1) - fpowInt(q, L)) / (q - 1);
}

int solve(LL L, LL R, const int& k, const int& m) {
  static Int pa[MAXK], pb[MAXK], px[MAXK], py[MAXK], A, x;
  int lgt = (R - L + 1) % P;
  if (m == 2)
    Sqrt = 5, A = Int(0, 1) / 5, x = Int(1, 1) / 2, ++L, ++R;
  if (m == 3)
    Sqrt = 3, A = Int(3, 1) / 6, x = Int(2, 1), L = (L + 1) / 2, R /= 2;
  if (L > R) return 0;
  pa[0] = pb[0] = px[0] = py[0] = 1;
  for (int i = 1; i <= k; ++i) {
    pa[i] = pa[i - 1] * A, pb[i] = pb[i - 1] * conj(A);
    px[i] = px[i - 1] * x, py[i] = py[i - 1] * conj(x);
  }
  Int ret = 0;
  for (int i = 0; i <= k; ++i) {
    Int s = 0;
    for (int j = 0; j <= i; ++j)
      s += Sum(L, R, px[j] * py[i - j]) * pa[j] * pb[i - j] * C(i, j);
    ret += s * stl[k][i];
  }
  return mul(fpow(lgt, P - 2), mul(ifac[k], ret.x));
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti, m, k;
  scanf("%d%d", &Ti, &m);
  PreDone(MAXK - 1);
  for (LL L, R; Ti; --Ti)
    scanf("%lld%lld%d", &L, &R, &k), printf("%d\n", solve(L, R, k, m));
  return 0;
}

「BJOI2019」送别

题目链接

https://loj.ac/problem/3091

解题思路

送别 $\times$, 带走 $\checkmark$

「BJOI2019」排兵布阵

题目链接

https://loj.ac/problem/3092

解题思路

这是一道定位在 NOIP Day 1 T2 的送分题 (

考虑 DP. 首先每个城堡和对手完全独立, 互不干扰. 设 $f(i, j)$ 表示已考虑完前 $i$ 个城堡, 小 C 剩余 $j$ 名士兵的得分最大值. 有

$f(i, j) = \max_{k} \{ f(i - 1, j - k) + w(i, k)\}$

其中 $w(i, k)$ 表示对于城堡 $i$ 派遣 $k$ 名士兵, 所有对局的总得分. 显然有 $O(s)$ 的暴力计算方法, 将对手派遣士兵个数从小到大排序, 依次枚举, 可以 $O(1)$ 的时间内转移.

时间复杂度 $O(nms)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3092
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

template<typename T> inline bool ckmax(T& a, const T& b) {
  return (a < b)? a = b, true: false;
}

const int MAXN = 1e2 + 5, MAXM = 2e4 + 5;

int s, n, m;
int A[MAXN][MAXN], f[MAXN][MAXM];

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%d%d%d", &s, &n, &m);
  for (int w, i = 1; i <= s; ++i)
    for (int j = 1; j <= n; ++j) scanf("%d", &w), A[j][i] = 2 * w + 1;

  int *w, ans = 0;
  for (int i = 1; i <= n; ++i) {
    w = A[i], sort(w + 1, w + 1 + s);
    for (int j = 0; j <= m; ++j) {
      for (int k = 0; k <= s && j >= w[k]; ++k)
        ckmax(f[i][j], f[i - 1][j - w[k]] + k * i);
      ckmax(ans, f[i][j]);
    }
  }

  printf("%d\n", ans);
  return 0;
}

「BJOI2019」光线

题目链接

https://loj.ac/problem/3093

解题思路

这是一道物理题, 难点在于推式子.

设 $f_i$ 表示前 $i$ 层玻璃, 从第 $1$ 层玻璃射入光的透光率. 那么 $f_n$ 即为答案. 此时问题仍不好解决, 因为没有考虑到反射对答案的影响. 那么设 $g_n$ 表示从第 $n$ 层玻璃向上射入光的反射率. 因此有

$f_n = a_n \cdot f_{n - 1} \sum_{k = 0} ^ \infty (g_{n - 1} b_n) ^ k = a_n \cdot \frac{f_{n - 1}}{g_{n - 1} b_n}$

表示透过第 $n$ 层的光来自上一层透过的光, 以及反射到上一层, 从而对本层做出贡献的部分.

$g_n = b_n + {a_n} ^ 2 g_{n - 1} \sum_{k = 0} ^ \infty (g_{n - 1} b_n) ^ k = b_n + \frac{ {a_n} ^ 2 g_{n - 1}}{g_{n - 1} b_n}$

表示光在第 $n$ 层反射的贡献 ($b_n$), 另外有透过第 $n$ 层 (乘上 $a_n$), 并再次在第 $n - 1$ 层反射回来, 或是多次反射 ($g_{n - 1} \sum\limits_{k = 0} ^ \infty (g_{n - 1} b_n)$), 通过第 $n$ 层玻璃 (在原有基础上乘 $a_n$) 的部分.

递推计算即可. 时间复杂度 $O(n \log P)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3093
// DeP
#include <cctype>
#include <cstdio>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

const int MAXN = 5e5 + 5, P = 1e9 + 7, iv100 = 570000004;

void exgcd(int a, int b, int& x, int& y) {
  if (!b) x = 1, y = 0;
  else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int inv(const int& a) {
  static int x, y;
  return exgcd(a, P, x, y), (x % P + P) % P;
}

int n;
int A[MAXN], B[MAXN], f[MAXN], g[MAXN];

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(A[i]), read(B[i]);
    A[i] = 1LL * A[i] * iv100 % P, B[i] = 1LL * B[i] * iv100 % P;
  }

  f[1] = A[1], g[1] = B[1];
  for (int i = 2; i <= n; ++i) {
    int iv = inv((1 - 1LL * B[i] * g[i - 1] % P + P) % P);
    f[i] = 1LL * A[i] * f[i - 1] % P * iv % P;
    g[i] = (B[i] + 1LL * A[i] * A[i] % P * g[i - 1] % P * iv % P) % P;
  }

  printf("%d\n", f[n]);
  return 0;
}

「BJOI2019」删数

题目链接

https://loj.ac/problem/3094

解题思路

可以发现每个数的位置在查询答案时是没有影响的. 如果将所有数丢到一个桶里, 即统计每个数的出现次数, 形成一个柱状的结构. 那么, 对于一次询问, 相当于将所有数向按值域所在位置向左填充, 或者形象地, 将柱子向左推倒. 此时 $[1, n]$ 中未覆盖位置即为答案.

同时要注意最大数 $> n$, 此部分贡献单独统计 —- 因为一定会被修改, 而不能同前文一样计算向左覆盖的位置. 正确性证明大概是先证明此时得出的结果是所有答案的下界, 并将所有重复填充的位置选择一部分修改, 一定能达到这个下界.

现在的问题在于如何维护这个过程, 考虑用线段树去维护这个桶, 即维护每个位置被覆盖的次数.

对于计算答案, 记录区间最小值, 以及最小值出现的次数. 那么, 一个区间能做出贡献, 当且仅当该区间未被覆盖, 即区间最小值为 $0$, 用最小值出现次数更新答案即可. 向上合并时直接将子区间答案合并即可.

对于 $p > 0$, 维护区间加的标记即可. 注意单独统计贡献的部分无需计算覆盖位置, 以及下传标记时需统计答案.

对于 $p = 0$, 也就是全局修改. 对应在桶中的影响, 也就是整体位移. 直接记录当前桶中 $0$ 的位置 $p_0$, 每次对应修改 $p_0$ 即可, 那么查询的区间为 $[p_0 + 1, p_0 + n]$.

值得留意的地方依旧是 $> p_0 + n$ 的位置, 注意加上 / 减去边界的覆盖情况.

时间复杂度 $O(m \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3094
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

const int MAXN = 1.5e5 + 5, MAXM = MAXN << 2;

int n, m, p0, N;
int A[MAXN], bkt[MAXM];

namespace SGT {
#define lc (nd << 1)
#define rc (nd << 1 | 1)
  int Mn[MAXM << 2], Cnt[MAXM << 2], dat[MAXM << 2], tag[MAXM << 2];

  inline void maintain(const int& nd) {
    dat[nd] = dat[lc] + dat[rc];
    Mn[nd] = min(Mn[lc], Mn[rc]);
    Cnt[nd] = (Mn[lc] == Mn[nd]) * Cnt[lc] + (Mn[rc] == Mn[nd]) * Cnt[rc];
  }
  inline void push(const int& nd, const int& v) {
    tag[nd] += v, Mn[nd] += v, dat[nd] = (Mn[nd] == 0) * Cnt[nd];
  }
  inline void pushdown(const int& nd) {
    if (tag[nd] != 0)
      push(lc, tag[nd]), push(rc, tag[nd]), tag[nd] = 0;
  }

  void build(int nd, int L, int R) {
    if (L == R)
      return void( Cnt[nd] = dat[nd] = 1 );
    int Mid = (L + R) / 2;
    build(lc, L, Mid), build(rc, Mid + 1, R);
    maintain(nd);
  }

  void Mdy(int nd, int L, int R, const int& opL, const int& opR, const int& v) {
    if (opL <= L && R <= opR) return push(nd, v);
    int Mid = (L + R) / 2;
    pushdown(nd);
    if (opL <= Mid) Mdy(lc, L, Mid, opL, opR, v);
    if (opR > Mid) Mdy(rc, Mid + 1, R, opL, opR, v);
    maintain(nd);
  }

  int Qry(int nd, int L, int R, const int& opL, const int& opR) {
    if (opL <= L && R <= opR) return dat[nd];
    int Mid = (L + R) / 2;
    pushdown(nd);
    if (opR <= Mid) return Qry(lc, L, Mid, opL, opR);
    if (opL > Mid) return Qry(rc, Mid + 1, R, opL, opR);
    return Qry(lc, L, Mid, opL, opR) + Qry(rc, Mid + 1, R, opL, opR);
  }
#undef lc
#undef rc
}

inline void Mdy(const int& v, const int& d) {
  int p = (d > 0)? v - bkt[v]: v - bkt[v] + 1;
  SGT::Mdy(1, 1, N, p, p, d), bkt[v] += d;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n), read(m);
  for (int i = 1; i <= n; ++i) read(A[i]);

  N = (m + n) * 2 + 1, p0 = m + n;
  SGT::build(1, 1, N);
  for (int i = 1; i <= n; ++i) A[i] += p0, Mdy(A[i], 1);

  for (int p, x; m; --m) {
    read(p), read(x);
    if (p > 0) {
      if (A[p] <= p0 + n) Mdy(A[p], -1); else --bkt[A[p]];
      A[p] = p0 + x;
      if (A[p] <= p0 + n) Mdy(A[p], 1); else ++bkt[A[p]];
    } else {
      p = (x < 0)? (p0 + 1) + n: p0 + n;
      if (bkt[p] > 0)
        SGT::Mdy(1, 1, N, p - bkt[p] + 1, p, -x);
      p0 -= x;
    }
    printf("%d\n", SGT::Qry(1, 1, N, p0 + 1, p0 + n));
  }
  return 0;
}

DepletedPrism's Blog

BJOI 2019 简要题解

「BJOI2019」奥术神杖

题目链接

解题思路

代码实现

「BJOI2019」勘破神机

题目链接

解题思路

代码实现

「BJOI2019」送别

题目链接

解题思路

「BJOI2019」排兵布阵

题目链接

解题思路

代码实现

「BJOI2019」光线

题目链接

解题思路

代码实现

「BJOI2019」删数

题目链接

解题思路

代码实现