本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 11:19:27

转换器：

Usage: .\/online raw.in raw.ans dst.in

dst.out 和 raw.ans 自然是一样的。

#include <iostream>
using namespace std;

int main (int argc, const char **argv)
{
	FILE *in, *out, *ans;
	int n, q, last = 0;

	in = fopen (argv[1], "r"), out = fopen (argv[2], "r"), ans = fopen (argv[3], "w");
	fscanf (in, "%d %d", &n, &q);
	fprintf (ans, "%d %d\n", n, q);
	for (int i = 0, v; i < n; i++) fscanf (in, "%d", &v), fprintf (ans, "%d ", v);
	fprintf (ans, "\n");
	while (q--) {
		int l, r;
		fscanf (in, "%d %d", &l, &r);
		if (l > r) swap (l, r);
		fprintf (ans, "%d %d\n", l ^ last, r ^ last);
		fscanf (out, "%d", &last);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 14:43:58

非常毒瘤的分桃题。

维护每个数的补后继，记作 $s(x)$；再设 $Q(x)$ 表示与 $x$ 相同的数组成的下标集合。

对 $Q(x)$，只有最大的那个下标能得到 $s(x)$，其他的 $s(x)$ 都是零，显然是正确的。

我们用 set 维护 $Q(x)$ 即可。然后考虑点修。

点修 $x$ 为 $y$ 后会导致什么？设 $x$ 上原来为 $u$，那么 $Q(u)$ 中要删去 $x$，$Q(y)$ 中加上 $x$。

• 如果 $x$ 是原来 $Q$ 中最小的，那么将以 $x$ 为补后继的数的补后继更新为 $x$ 的等后继

• 如果 $x$ 原来是 $Q$ 中最大的，那么更新其等前驱的补后继

• 如果 $x$ 是现在 $Q$ 中最小的，那么将以 $y$ 为补后继的数的补后继更新为 $x$

• 如果 $x$ 是现在 $Q$ 中最大的，那么从其等前驱抢来补后继

上面那几把东西假了。

$x$ 原来的后继？要给比 $x$ 大的且比 $x$ 原来后继小的，即最大的小于 $x$ 原后继的在 $Q$ 中的。

原来以 $x$ 为后继的？给 $Q(x)$ 中最小的大于原来以 $x$ 为后继的。

$x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ 是最小的大于 $x$ 的。

以 $y$ 为后继的？找第一个大于其的。

-- upd 7.29

这个题看起来并没有那么难。

我们设一个数 $x$ 的前驱，为 $w - x$ 的位置，那么问题就转化为求区间前驱的最大值，看它是不是不小于 $l$。

我们考虑点修带来的变化。首先发现，对于两个有相同前驱的数，下标大的那个的前驱是不需要维护的。

那么这样，我们就只保留一堆数字中最靠前的那个数的前驱位置，其他的就扔掉不管。

现在考虑点修。

首先，如果有 $y$ 使得 $p(y) \ne x$ 且 $y \ne p(x)$ 的，那么 $y$ 是不会变的。

对于以 $x$ 为前驱的数，我们找和 $x$ 相同的，且最靠右的那个来替换。

然后，我们把 $x$ 原来的前驱让给和他相等的最靠左的那个。

这样，$x$ 就能大胆得变成别的数了。设 $x$ 变成了 $y$，那么如果 $x$ 的位置比 $y$ 里头最靠前的还要靠前（同时肯定要在它的前驱后头），那么就把原来 $y$ 的前驱抢过来；

如果以 $y$ 为前驱的数，这时候如果 $x$ 是最大的，我们就把原来前驱替换成 $x$。

这样之后，我们做区间最大值就可以了。线段树搞定。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 20:12:11

const int N = 1e5 + 10, oo = 2147483647;
int fa[N << 6], son[N << 6][2], siz[N << 6], cntq[N << 6], val[N << 6], rt[4 * N], cnt = 1, z[N], n;

namespace splay {
static inline void maintain (int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
static inline int get (int x) { return x == son[fa[x]][1]; }
static inline int compare (int f, int k) { return k > val[f]; }
static inline void rotate (int x)
{
    int y = fa[x], z = fa[y], p = get (x);
    son[y][p] = son[x][p ^ 1];
    if (son[x][p ^ 1]) fa[son[x][p ^ 1]] = y;
    fa[fa[son[x][p ^ 1] = y] = x] = z;
    if (z) son[z][y == son[z][1]] = x;
    maintain (y), maintain (x);
}

static inline int splay (int &rt, int x, int t = 0)
{
    for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
        if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
    return t ? x : rt = x;
}

static inline int insert_at (int f, int k)
{
    siz[cnt] = cntq[cnt] = 1, val[cnt] = k, fa[cnt] = f;
    if (f) son[f][compare (f, k)] = cnt;
    return cnt++;
}

static inline int insert (int &rt, int k)
{
    int f = rt, last = 0;
    if (!f) return rt = insert_at (0, k);
    while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
    if (f && val[f] == k) return cntq[f]++, splay (rt, f);
    else return f = insert_at (last, k), maintain (last), splay (rt, f);
}

static inline int find (int &rt, int k)
{
    int f = rt;
    if (!f) return 0;
    while (val[f] != k && son[f][compare (f, k)]) f = son[f][compare (f, k)];
    return splay (rt, f);
}

static inline int merge (int &rt, int x, int y)
{
    int f = x;
    if (!x || !y) return x + y;
    while (son[f][1]) f = son[f][1];
    son[splay (rt, f, fa[x])][1] = y;
    if (y) fa[y] = f;
    return f;
}

static inline int remove (int &rt, int k)
{
    int f = find (rt, k), x;
    if (cntq[f] > 1) return cntq[f]--, splay (rt, f);
    if ((x = merge (rt, son[f][0], son[f][1]))) fa[x] = 0;
    return rt = x;
}

static inline int qnxt (int &rt, int k)
{
    int f = son[find (rt, k)][1];
    if (val[rt] > k) return rt;
    while (son[f][0]) f = son[f][0];
    return splay (rt, f);
}

static inline int qpre (int &rt, int k)
{
    int f = son[find (rt, k)][0];
    if (val[rt] < k) return rt;
    while (son[f][1]) f = son[f][1];
    return splay (rt, f);
}

static inline int qrank (int &rt, int k) { return siz[son[find (rt, k)][0]] + (val[rt] < k ? cntq[rt] : 0); }
}

namespace segtree {
static inline void build (int i, int x, int y)
{
    int mid = (x + y) \/ 2;
    splay::insert (rt[i], oo), splay::insert (rt[i], -oo);
    if (x != y) build (i * 2, x, mid), build (i * 2 + 1, mid + 1, y);
}

static inline void insert (int i, int x, int y, int p, int k)
{
    int mid = (x + y) \/ 2;
    splay::insert (rt[i], k);
    if (x == y) return;
    if (p <= mid) insert (i * 2, x, mid, p, k);
    else insert (i * 2 + 1, mid + 1, y, p, k);
}

static inline int qrank (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) \/ 2, res = 0;
    if (l <= x && y <= r) return splay::qrank (rt[i], k) - 1;
    if (l <= mid) res = qrank (i * 2, x, mid, l, r, k);
    if (r > mid) res += qrank (i * 2 + 1, mid + 1, y, l, r, k);
    return res;
}

static inline void upd (int i, int x, int y, int p, int k)
{
    int mid = (x + y) \/ 2;
    splay::remove (rt[i], z[p]), splay::insert (rt[i], k);
    if (x == y) return z[p] = k, void ();
    if (p <= mid) upd (i * 2, x, mid, p, k);
    else upd (i * 2 + 1, mid + 1, y, p, k);
}

static inline int qpre (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) \/ 2, res = -oo;
    if (l <= x && y <= r) return val[splay::qpre (rt[i], k)];
    if (l <= mid) res = qpre (i * 2, x, mid, l, r, k);
    if (r > mid) res = max (res, qpre (i * 2 + 1, mid + 1, y, l, r, k));
    return res;
}

static inline int qnxt (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) \/ 2, res = oo;
    if (l <= x && y <= r) return val[splay::qnxt (rt[i], k)];
    if (l <= mid) res = qnxt (i * 2, x, mid, l, r, k);
    if (r > mid) res = min (res, qnxt (i * 2 + 1, mid + 1, y, l, r, k));
    return res;
}

static inline void build (void) { build (1, 1, n); }
static inline void insert (int p, int k) { insert (1, 1, n, p, k); }
static inline int qrank (int l, int r, int k) { return qrank (1, 1, n, l, r, k); }
static inline void upd (int p, int k) { upd (1, 1, n, p, k); }
static inline int qpre (int l, int r, int k) { return qpre (1, 1, n, l, r, k); }
static inline int qnxt (int l, int r, int k) { return qnxt (1, 1, n, l, r, k); }
static inline int kth (int x, int y, int k)
{
    int l = 0, r = 1e9, mid, ans = -1;
    while (l <= r) {
        mid = (l + r) \/ 2;
        if (qrank (x, y, mid) + 1 <= k) l = (ans = mid) + 1;
        else r = mid - 1;
    }
    return ans;
}
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-12 12:21:14

void add (int x, int k) { while (x <= n && k > f[x]) f[x] = k, x += lowbit (x); }

int qry (int x, int y)
{
    int res = -1e9;
    while (y >= x) {
        if (y - lowbit (y) > x) res = max (res, f[y]), y -= lowbit (y);
        else res = max (res, z[y]), y--;
    }
    return res;
}

即树状数组求区间最值。

点加的复杂度是显然的。考虑区间查。

$y$ 有两种变化：

• 减去 $\text{lowbit} (y)$
• 减去一

不难发现 $y$ 的减量是不小于一的。然后发现对于情况二，$y$ 的低 $\text{highbit(x)}$ 位一定全都是 $0$，那么这种情况出现次数是 $\log$ 级别的。情况二后紧跟的一定是操作一（因为 $\text{lowbit}(y) \gets 1$），这之后是连续 $\log$ 次的操作一。所以粗略复杂度是 $O(\log^2 n)$。

感性上这个上界有点松了。但我不太会势能分析。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 11:04:43

设 $f(u, k)$ 代表在 $u$ 的子树上，需要删掉多少条边才能得到一个大小为 $k$ 的子树。初始地，$f(u, 1) = 0$，$f(u,k) = \infty \space \text{s.t.} \space k \neq 1$。

那么对于每一个孩子，我们如果不用它，那么就是 $f(u, k) + 1$，因为需要删掉这条边。

否则，如果用这个孩子 $v$ 来更新 $u$，我们就有：

$f(u, k) = f(u, j) + f(v, k - j), \space 0 \le j \le k - 1$

所以总的方程：

$$ f(u, k) = \min\limits_{v} f(u, k) + 1, f(u, j) + f(v, k - j) $$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-20 21:52:17

主席树就是可持久化权值线段树。因为线段树本身就比平衡树常数小，并且它是严格 $\Theta(\lg n)$ 而不是摊下来的，所以说 “能离线的都用线段树” —— 崔神语。

主席树板子是区间的第 $k$ 小问题，P3834。读一下题，你会发现这题甚至都没有在不在线的区别。

我们先考虑怎么维护 $[1, r]$ 内的第 $k$ 小。这就和平衡树的 kth 差不多。建一个值域线段树，对区间维护一个 sum，表示区间内有多少个数。那么显然，我们只需要根据当前区间数的数量来判断走左还是右子树即可，单查询 $\Theta(\lg n)$，总复杂度 $O(n\lg n + q\lg n)$，因为带了一个离散化。

再考虑 $[l, r]$ 的第 $k$ 小。这玩意儿一般人按说是没法忍住不继续看下文的情况下能自己想出来的。我们用可持久化线段树维护每一个历史版本，然后 $[l, r]$ 的查询就变成了个前缀和，同样复杂度可做，但是空间从 $O(n)$ 到了 $O(n + q\lg n)$。

模板懒得写了，随便抄个题解就过了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 10:03:14

我们保存每一个点开始搜集情报的时间 $t_i$，那么操作二就是显然的设置，操作一就是问区间有多少个小于 $t - c$ 的 $t_i$，主席树即可，而且不用离散化。

这么一看这题也太简单了，裸树剖套了个主席树板子 + LCA，亏我昨晚上想一晚上。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-08 20:37:11

很明显就是线段树维护区间次小值的出现次数。

这里主要讲怎么把 push_up 写的简洁一些。

node
push_up (const node &l, const node &r)
{
  vector<pi> z; z.reserve (4);
  
  z.emplace_back (l.mx), z.emplace_back (l.pmx);
  z.emplace_back (r.mx), z.emplace_back (r.pmx);
  sort (begin (z), end (z), greater<pi> ());
  for (auto p = begin (z); p != prev (end (z)); p++)
    if (p->first == next (p)->first) p->second += next (p)->second;
  return { z[0], z[1].first == z[0].first ? z[2] : z[1] };
}

某些人写了六十行的大模拟还没调过

我们可以把值和出现次数捆绑在一起维护，这样就可以方便更新。先排序，然后维护一下出现次数即可。

完整代码（只有 74 行）

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-21 15:05:14

和机房 dalao 在机房黑板上推了式子，但是不如队爷 cxm 的简洁，替他 写个题解。

这题和百事世界杯那道很像，区别就是这题是有两个人的。 但是状态是一样的。

我们设 $f(x)$ 表示作为先手，当前有 $x$ 个物品已经被摸到的期望代价，同理设 $g(x)$ 代表后手的相应情况。（用 $i$ 做变量的话推式子老觉得跟复分析一样qwq）

对于每一次摸球，我们只有摸到新的和摸到旧的两种可能。

• 摸到新的，概率是 $\dfrac {n - x} n$，此时有

$$\begin{cases} f(x) = g(x + 1), \ g(x) = f(x + 1) \end{cases}$$

• 摸到旧的，概率是 $\dfrac x n$，此时

$$\begin{cases} f(x) = g(x) + 1, \ g(x) = f(x) \end{cases}$$

这个先后手的转移有一点抽象。当前的先手，转移之后自然是后手，反之亦然。这里玩家并没有改变，仍然是 A 和 B，只是先后手的顺序改变了。我们用状态，用的就是它的语义。

联立这个方程，得到解：

$$\begin{cases} f(x) = \bigg(\dfrac {n - x} n \cdot g(x + 1) + \dfrac{x\cdot (n - x)}n \cdot f(x + 1) + \dfrac x n\bigg) \bigg/ \bigg(1 - \dfrac {x^2}{n^2}\bigg) \ g(x) = \dfrac x n \cdot f(x) + \dfrac{n - x}n \cdot f(x + 1) \end{cases}$$

倒着递推就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-28 17:24:24

卢卡斯定理即

$${n \choose m} \equiv {\lfloor n/p \rfloor \choose \lfloor m/p\rfloor} \cdot {n \bmod p \choose m \bmod p} \pmod p$$

其中 $p$ 是质数

我们用二项式定理证明。

首先，$p$ 是质数，则 $${p\choose n} = p n^{-1} {p-1 \choose n-1} \equiv 0 \pmod p$$

然后有

$$(x+1)^p = \sum\limits_{j=0}^p {p \choose j} x^j \equiv x^p + 1 \pmod p$$

然后构造

$$ \begin{aligned} (x + 1)^m &\equiv (x+1)^{p\lfloor m / p\rfloor + (m \bmod p)} \ &\equiv (x^p + 1)^{m/p} (x+1)^{m \bmod p} \ &\equiv \sum\limits_{j=0}^{\lfloor m/p\rfloor} {\lfloor m/p\rfloor \choose j}x^{jp} \cdot \sum\limits_{k=0}^{m\bmod p}{m \bmod p \choose k}x^k \ &\equiv \sum\limits_{k=0}^{m} {\lfloor m/p\rfloor \choose \lfloor m/k\rfloor}{m \bmod p \choose k \bmod p} \pmod p \end{aligned} $$

又有

$$(x+1)^m =\sum\limits_{k=0}^m {m\choose k}x^k$$

按系数，得证：

$${\lfloor m/p\rfloor\choose \lfloor m/k\rfloor}{m\bmod p\choose k\bmod p} \equiv {m\choose k} \pmod p$$