拟阵 $M=(S,I)$，其中 $S$ 是事件的集合，$I$ 是 $S$ 的子集的集合，满足一定的限制条件。拟阵有如下的定义（性质）：

• 遗传性：若 $A\in I$，则 $\forall A^*\subseteq A,A^*\in I$；
• 交换性：$\forall A,B\in I,|A|<|B|$，有 $\exists x\in B\setminus A$，使得 $A\cup\{x\}\in I$。

有这样一类问题，让你选择一个 $I$ 的子集 $I^*$，使得 $\sum_{x\in I^*}f(x)$ 最大，其中 $f(x)$ 是一个，一个一个一个一个。

link.

对于 pass 1, 你把他考虑成 $\frac{\sum x}{i}$ 的形式, 于是每次操作的贡献就是 $\frac{2}{i}$, 那么答案就是 $\sum_{i=2}^n\frac{2}{i}$.

对于 pass 2, 首先由全概率公式 $\textbf{E}(n)=\sum_{i=0}^{\infty}\textbf{P}(n\geqslant i)$. 那么我们考虑固定 $k=i$, 求出 $\textbf P(n\geqslant k)$. 其实直接求这个有点麻烦, 强化一下条件, 我们求 $\textbf P(n=k)$, 最后后缀和即可取得 $\textbf P(n\geqslant k)$.

设 $f(i,j)$ 表示共 $i$ 个叶结点, 树深度为 $j$ 时的概率. 对于二叉树我们有一种经典的考虑子结构的方式, 即考虑左子树的信息. 对于此题, 我们考虑左子树 (相对于根结点来说) 的叶结点数量 $k$. 那么有 $f(i,\max\{k,l\}+1)\gets f(i,\max\{k,l\}+1)+\frac{f(j,k)\times f(i-j,l)}{i-1}$. 其中 $i$ 为全树的叶子个数, $k$, $l$ 分别为左, 右子树的深度, $j$ 为左子树的叶结点个数. $\frac{1}{i-1}$ 是对于一个有 $i$ 个叶子的二叉树, 有 $k$ 个结点在左子树的概率, which 与 $k$ 无关. 至于为什么是 $\frac{1}{i-1}$, 你考虑操作次数为 $i-1$ 即可.

#include <bits/stdc++.h>
using namespace std;
typedef double db;
int Q, N;
db f[200][200];
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> Q >> N;
  cout << fixed;
  cout << setprecision(6);
  if (Q == 1) {
    db ans = 0;
    for (int i = 2; i <= N; ++i) {
      ans += 2.0 / i;
    }
    cout << ans << "\n";
  } else if (Q == 2) {
    f[1][0] = f[2][1] = f[3][2] = 1;
    for (int i = 4; i <= N; ++i) {
      for (int j = 1; j < i; ++j) {
        for (int k = 0; k < j; ++k) {
          for (int l = 0; l < i - j; ++l) {
            f[i][max(k, l) + 1] += f[j][k] * f[i - j][l] / (i - 1);
          }
        }
      }
    }
    db ans = 0;
    for (int i = N; i >= 1; --i) {
      f[N][i] += f[N][i + 1];
    }
    for (int i = 1; i < N; ++i) {
      ans += f[N][i];
    }
    cout << ans << "\n";
  }
  return 0;
}

link。

非常离谱, 但它确实在 loj fastest rank 2 站着.

我们首先看得出来这是个无脑分讨题, 考虑怎么能减少点讨论 (motivation) (不).

constructive method: 令 $x'_i=x_i-y_i$, $y'_i=x_i+y_i$, 然后绝对值相加就变成绝对值取 $\max$ 蜡!

但是是个 trivial trick (?), 小丑了.

然后就排序第一个关键字, 二分答案再 check 构造答案即可.

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
#define int ll
int N, K, ans[250100], cnt;
pii p[250100];
set<pii> s;
set<pii>::iterator it;
ll dist(int x, int y) {
  return max(abs(p[x].first - p[y].first), abs(p[x].second - p[y].second));
}
bool check(ll M) {
  cnt = 0;
  s.clear();
  for (int i = 1, t = 1; i <= N; ++i) {
    while (t < i && p[i].first - p[t].first > M) {
      // 固定第一维
      s.erase(mp(p[t].second, t));
      t++;
    }
    it = s.lower_bound(mp(p[i].second - M, 0));
    for (; it != s.end(); ++it) {
      if (it->first - p[i].second > M) {
        break;
      }
      ans[++cnt] = dist(it->second, i);
      if (cnt >= K) return 0;
    }
    s.insert(mp(p[i].second, i));
  }
  return cnt < K;
}
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> N >> K;
  for (int i = 1, x, y; i <= N; ++i) {
    cin >> x >> y;
    p[i] = mp(x - y, x + y);
  }
  sort(p + 1, p + N + 1);
  ll l = 0, r = 4e9, Mid, res = 0;
  while (l <= r) {
    if (check(Mid = (l + r) / 2)) {
      l = Mid + 1, res = Mid;
    } else {
      r = Mid - 1;
    }
  }
  check(res);
  sort(ans + 1, ans + cnt + 1);
  for (int i = 1; i <= cnt; ++i) {
    cout << ans[i] << "\n";
  }
  for (int i = cnt + 1; i <= K; ++i) {
    cout << res + 1 << "\n";
  }
  return 0;
}

link.

感觉好久没写过题解了, 这就是永远在骚动的得不到吧.

星尘 infinity 真的非常行, 就算是 ja voicebase 都不知道吊打那群日 v 多少圈. 我推荐你们都去听一听.

chin voicebase 更是重量级, 乱杀 vs 那堆. 不得不说个体技术力质的进步才是社会发展的关键, 什么大家进步了总体就进步了就是扯淡.

当然也不能像赫鲁晓夫那群天才一样鼓吹唯生产力论, 但是用 $+\infty$ 的 p 们确实交出了优秀的答卷, 时至今日的格局只能说是原本基础决定的.

首先如果没有删除操作的话, 这题可以 parallel search 随便做做了. 加上删除操作再套个 segment tree beats 就行.

题解大概就是这样, 我主要来说下这个 segment tree beats. 首先这里没有必要真的写一个出来, 因为注意到是单点询问. 但是这里的线段树有一些不同于传统的线段树, 尽管传统线段树也是一棵 leafy tree, 但是这里树的非叶结点上是没有信息需要维护的. 可以把 lazy propagation 和你维护的幺半群放到一个数组来写.

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

const i64 inf = 1e9;
int N, M, Q, sz, h, ans[250100];
i64 dat[250100];
struct rec {
  i64 p, q;
} lz[524388];
struct req {
  i64 a, b, c, d;
} q[250100];
void add(int x, i64 v) {
  for (; x <= N + 1; x += x & -x) dat[x] += v;
}
void add(int l, int r, i64 v) { add(l, v), add(r + 1, -v); }
i64 sum(i64 x) {
  i64 res = 0;
  for (; x; x -= x & -x) res += dat[x];
  return res;
}
rec composition(rec f, rec v) { return {v.p + f.p, max(v.q + f.p, f.q)}; }
void propagate(int x, rec f) { lz[x] = composition(f, lz[x]); }
void push(int x) {
  propagate(x * 2, lz[x]), propagate(x * 2 + 1, lz[x]), lz[x] = {0, -inf};
}
void add(int l, int r, rec f) {
  assert(0 <= l && l <= r && r <= N);
  if (l == r) return;
  l += sz, r += sz;
  for (int i = h; i >= 1; --i) {
    if (((l >> i) << i) != l) push(l >> i);
    if (((r >> i) << i) != r) push((r - 1) >> i);
  }
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) propagate(l++, f);
    if (r & 1) propagate(--r, f);
  }
}
i64 get(i64 x) {
  assert(0 <= x && x < N);
  for (i64 i = h; i >= 1; --i) push((x + sz) >> i);
  return max(lz[x + sz].p, lz[x + sz].q);
}

void dac(int l, int r, const vector<int>& id) {
  if (id.empty()) return;
  if (l == r) {
    for (auto&& it : id) ans[it] = l;
    return;
  }
  int mid = (l + r) / 2;
  for (int i = l; i <= mid; ++i)
    if (q[i].c && q[i].d) add(q[i].a, q[i].b, q[i].d);
  vector<int> ql, qr;
  for (auto&& it : id) (sum(q[it].a) >= q[it].b ? ql : qr).emplace_back(it);
  dac(mid + 1, r, qr);
  for (int i = l; i <= mid; ++i)
    if (q[i].c && q[i].d) add(q[i].a, q[i].b, -q[i].d);
  dac(l, mid, ql);
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> N >> M >> Q;
  h = ceil(log2(N)), sz = 1 << h;
  for (int i = 0; i <= N; ++i) lz[i + sz] = {0, -inf};
  vector<int> is;
  for (i64 o, l, r, c, k, i = 1; i <= Q; ++i) {
    cin >> o >> l >> r, c = k = 0;
    if (o == 1)
      cin >> c >> k, add(l, r, k), add(l - 1, r, {k, 0});
    else if (o == 2)
      cin >> k, add(l - 1, r, {-k, 0});
    else
      r += sum(l) - get(l - 1), is.emplace_back(i);
    q[i] = {l, r, c, k};
  }
  memset(dat, 0, sizeof(dat)), dac(1, Q + 1, is);
  for (int i = 1; i <= Q; ++i)
    if (q[i].c == 0 && q[i].d == 0)
      cout << q[ans[i] > i ? 0 : ans[i]].c << "\n";
  return 0;
}

一个被国内 oi 环境弱化至几乎不存在的概念，不过我觉得还是有学一学的必要。因为我没学过代数结构所以大部分内容都在开黄腔，欲喷从轻。

Semigroup 的定义是，$\forall a,b\in\mathbb{S}$，有 $a\cdot b\in\mathbb{S}$ 并且 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$，则称 $\lang\mathbb{S},\cdot\rang$ 为一个 semigroup，称其中的二元运算 $\cdot:\mathbb{S}\cdot\mathbb{S}\rightarrow\mathbb{S}$ 为半群的乘法。

Semigroup 与 group 的区别在于有无幺（identity element），并且所有元素均有逆。

Monoid 则是在 semigroup 的基础上添加了一个幺，翻译过来即幺半群。

有了这些理论支撑，我们在解决一系列数据结构问题时的思维将得到几乎为零的简化