link。

称题目中的 $c_i$ 为 $a_i$，令 $c_i$ 为第 $i$ 种颜色的出现次数，令 $C$ 为颜色总数。固定 $k$，令 $t_i=1$，如果颜色 $i$ 被选择了一次及以上，否则为 $0$，则答案为 $\textbf{E}(\sum t_i)=\sum\textbf{E}(t_i)=\sum\frac{\binom{n}{k}-\binom{n-c_i}{k}}{\binom{n}{k}}$。

对于一个固定的 $k$，上式的取值只取决于 $c_i$ 的大小，令 $s_x$ 为 $c_i=x$ 的 $i$ 的数量。则答案写为 $\sum s_x\times\frac{\binom{n}{k}-\binom{n-x}{k}}{\binom{n}{k}}$。

分析复杂度，$n=\sum i\times s_i$，因此单次计算最劣 $\Theta(\sqrt n)$。

#include <bits/stdc++.h>

#include <atcoder/modint>
using mint = atcoder::modint998244353;
mint fac[50100], ifac[50100];
void preComb(int n) {
  fac[0] = ifac[0] = mint::raw(1);
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
  ifac[n] = fac[n].inv();
  for (int i = n - 1; i; --i) ifac[i] = ifac[i + 1] * (i + 1);
}
mint C(int n, int k) {
  if (n < k) return 0;
  return fac[n] * ifac[n - k] * ifac[k];
}
int c[50100], s[50100], n, a[50100];
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  std::cin >> n;
  preComb(n);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::vector<int> pri(a + 1, a + n + 1);
  std::sort(pri.begin(), pri.end());
  pri.erase(std::unique(pri.begin(), pri.end()), pri.end());
  int C = static_cast<int>(pri.size());
  for (int i = 1; i <= n; ++i)
    a[i] = std::lower_bound(pri.begin(), pri.end(), a[i]) - pri.begin() + 1;
  for (int i = 1; i <= n; ++i) ++c[a[i]];
  for (int i = 1; i <= C; ++i) ++s[c[i]];
  std::vector<int> vec;
  for (int i = 1; i <= n; ++i) {
    if (s[i]) vec.emplace_back(i);
  }
  for (int k = 1; k <= n; ++k) {
    mint res = 0;
    for (int x : vec) res += s[x] * (::C(n, k) - ::C(n - x, k));
    res *= ::C(n, k).inv();
    std::cout << res.val() << '\n';
  }
  return 0;
}

原来的标题是：『「水」CRT 的构造本质』。

对于一个单元线性同余方程组 $x\equiv a_i\pmod{r_i}$，考虑构造一个 $\{c_i\}$ 使得 $\forall i\neq j$，有 $c_i\equiv0\pmod{r_j}$，且 $c_i\equiv1\pmod{r_i}$，那么一定存在解 $x\equiv\sum a_ic_i\pmod{\prod r_i}$。

给出一种构造方法：令 $m_i=\frac{\prod r_i}{r_i}$，则 $c_i\equiv m_i\times m_i^{-1}$，其中 $m_i^{-1}$ 是 $m_i$ 模 $r_i$ 的乘法逆元（但运算结果不作取模），显然满足上述性质，这就是 Chinese Remainder Theorem 的构造本质。

其实这个的标题叫 平凡线段树上二分幻术，因为这是一个民科在乱叫。

如标题所言，这个东西确实非常 trivial。碍于网络上没有一个成体系的文章供参考就只能自己来炒炒冷饭。

如果出了什么 bug 就当个笑话看。

我们这样来描述一类问题

给出一个序列 $\{a_n\}$ 以及函数 $\textbf{f}(x)\in\{0,1\}$，在 $[l,r]$ 中查找满足 $\textbf{f}(a_i)=1$ 的所有位置所组成的集合中的一个元素，该元素满足某个指定的性质。

网络上大部分资料对这类问题的线段树二分做法只停留在全局查询。事实上，线段树二分的做法完全可以搬到区间上，做法并不困难。

以下令 $[l,r]$ 为线段树执行时的当前区间，$[x,y]$ 为询问区间。

我们在执行线段树的时候，维护一个标记 $g\in\{0,1\}=[[l,r]\subseteq[x,y]]$，如果为 $0$，则继续在线段树上搜寻询问区间，否则就执行二分，因为查询的结点数为 $\Theta(\log_2 n)$ 且树的深度为 $\Theta(\log_2 n)$，所以单次复杂度 $\Theta(\log_2 n)$。

例题大概是 codeforces - 407E，我负责给李涵口胡，然后李涵就把代码杠出来了。

阶（multiplicative order）

$\textbf{Def.}$：$\delta_m(a)$ 为最小的 $n$ 使得 $a^n\equiv 1\pmod m$，其中 $(a,m)=1$。

Observation 1：$\boxed{a^0\not\equiv a^1\not\equiv\dots\not\equiv a^{\delta_m(a)-1}\pmod m}$。

$\textbf{Proof}$：若 $\exists i,j,s.t.0\leqslant i<j<\delta_m(a),a^i\equiv a^j\pmod m$，则 $a^{i-j}\equiv 1\pmod m$，又 $i-j<\delta_m(a)$，矛盾。

$\blacksquare$

Observation 2：$\boxed{\delta_m(a)\mid\varphi(m)}$。

$\textbf{Proof}$：由欧拉定理： $a^{\varphi(m)}\equiv 1\pmod m$，因为 $1^x=1$，所以如果存在 $x_0$ 使得 $a^{x_0}\equiv 1\pmod m$，那么 $x_0$ 倍数也一定可以，也就是说存在周期性，所以 $\delta_m(a)\mid\varphi(m)$。BTW，同时也有若 $a^n\equiv 1\pmod m$，则 $\delta_m(a)\mid n$。

$\blacksquare$

顺便可以知道若 $a^p\equiv a^q\pmod m$，则 $p\equiv q\pmod{\delta_m(a)}$。

Lemma 1：设 $m\in\mathbb{N}^*$，$a,b\in\mathbb{Z}$，$(a,m)=(b,m)=1$，则 $\boxed{\delta_m(ab)=\delta_m(a)\delta_m(b)}$ 的重要条件是 $(\delta_m(a),\delta_m(b))=1$。

$\textbf{Proof}$：略，具体见此处。

Lemma 2：设 $k\in\mathbb{N}$，$m\in\mathbb{N}^*$，$a\in\mathbb{Z}$，$(a,m)=1$，则 $\boxed{\delta_m(a^k)=\frac{\delta_m(a)}{(\delta_m(a),k)}}$。

$\textbf{Proof}$：略，具体见此处。

原根（primitive root）

$\textbf{Def.}$：对于 $(a,m)=1$，若 $\delta_m(a)=\varphi(m)$，则称 $a$ 是模 $m$ 的原根。

Lemma 1（判定定理）：设 $m\geqslant3$，$(a,m)=1$，则 $a$ 为模 $m$ 的原根当且仅当 $\boxed{\forall p\in\mathbb{P},p\mid\varphi(m),a^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m}$。

$\textbf{Proof}$：必要性显然，充分性证明见此处。

Lemma 2（数量定理）：若 $m$ 存在原根，则其原根数量为 $\boxed{\varphi(\varphi(m))}$。

$\textbf{Proof}$：略，具体见此处。

Lemma 3（存在定理）：$m$ 存在原根当且仅当 $\boxed{m=2,4,p^\alpha,2p^\alpha}$，其中 $p$ 为奇素数，$a\in\mathbb{N}^*$。

$\textbf{Proof}$：略，具体见此处。

若 $m$ 存在原根，则最小原根 $\leqslant m^\frac{1}{4}$。

link。

首先对原序列排序，考虑静态序列做法为：设 $f(n,k\in\{0,1\})$ 为对于前 $n$ 个数，第 $n$ 个数否 / 是已经决策完毕的最优方案，转移即

$$ \begin{cases} f(n,0)=f(n-1,1) \\ \displaystyle f(n,1)=\lvert a(n)-a(n-1)\rvert+\min\{f(n-1,\{0,1\})\} \end{cases} $$

再由于增 / 减数操作，我们使用数据结构来维护，如果使用维护区间的数据结构那么区间 DP 是最好的选择。把状态换为 $f(l,r,k_1\in\{0,1\},k_2\in\{0,1\})$ 表示考虑区间 $[l,r]$，左 / 右端点分别否 / 是已经决策完毕。转移即

$$ f(l,r,k_1,k_2)=\min_{a+b>1}\{f(l,m,k_1,a),f(m,r,b,k_2)\} $$

注意使用不同的数据结构转移会有不同，此处为平衡树情况的转移。不过代码写的是线段树，请注意区分。$m$ 为 $[l,r]$ 中一点，也需要注意 $r-l\leqslant2$ 情况的特判。

省去了一些东西，完整代码见此处，特征码 cc-strquer。

const long long inf = 1e18;
namespace 😅😅 {
struct node {
  int ls, rs, num;
  long long l, r, mx, mn;
  long long dp[2][2];
  long long *const operator[](const long long i) { return dp[i]; }
} 😅[2 * 200000 * 60];
int tot;
int fuck😅(long long l, long long r) {
  int shit = ++tot;
  😅[shit].ls = 😅[shit].rs = 0;
  😅[shit].l = l, 😅[shit].r = r;
  😅[shit].num = 0;
  return shit;
}
void Merge(node &$😅, node x, node y) {
  node ap;
  bool flag = 0;
  if (!x.num) {
    ap = y;
    flag = 1;
  }
  if (!y.num) {
    ap = x;
    flag = 1;
  }
  if (flag) {
    $😅.mn = ap.mn;
    $😅.mx = ap.mx;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) $😅[i][j] = ap[i][j];
    }
    return;
  }
  $😅.mn = x.mn;
  $😅.mx = y.mx;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      $😅[i][j] = -inf;
      for (int a = 0; a < 2; ++a) {
        for (int b = 0; b < 2; ++b)
          Max($😅[i][j], x[i][a] + y[b][j] + a * b * (y.mn - x.mx));
      }
    }
  }
}
void add(int p, long long x, int v) {
  auto &l = 😅[p].l, &r = 😅[p].r;
  if (!p) p = ++tot;
  😅[p].num += v;
  if (l == r) {
    😅[p].mx = 😅[p].mn = x;
    😅[p][0][0] = 😅[p][1][1] = -inf;
    😅[p][0][1] = 😅[p][1][0] = 0;
    return;
  }
  long long mid = (l + r) >> 1;
  if (mid >= x) {
    if (!😅[p].ls) 😅[p].ls = fuck😅(l, mid);
    add(😅[p].ls, x, v);
  } else {
    if (!😅[p].rs) 😅[p].rs = fuck😅(mid + 1, r);
    add(😅[p].rs, x, v);
  }
  Merge(😅[p], 😅[😅[p].ls], 😅[😅[p].rs]);
}
}  // namespace 😅😅
signed main() {
  int T;
  for (cin > T; T; --T) {
    int n, q;
    cin > n > q;
    😅😅::fuck😅(0, inf);
    for (long long x; n; --n) {
      cin > x;
      😅😅::add(1, x, 1);
    }
    for (int t; q; --q) {
      long long x;
      cin > t > x;
      if (t == 0)
        😅😅::add(1, x, 1);
      else
        😅😅::add(1, x, -1);
      cout < 😅😅::😅[1].mx - 😅😅::😅[1].mn - imax(😅😅::😅[1][1][1], 0LL) < '\n';
    }
    😅😅::tot = 0;
  }
  return 0;
}