好吧既然补出来昨日T1那还是补一下吧。
[T1]
从上到下覆盖路径是困难的，考虑反转后从下往上做。
由于 N \leq 500，猜一猜是 O(N ^ 3) 的，于是考虑二维状态。
设 f_{u, k} 表示在覆盖 u 子树的前提下（包含 u），还覆盖了几个 u 的祖先。
对于子树更新，转移是比较好写的。
处理完子树后，考虑暴力上跳一一匹配前序节点并更新。
方案的记录比较烦，需要放在一起更新，否则可能导致复杂度不对。
实现具体见代码。
#include
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PIP;
#define x first
#define y second
const int N = 505, M = 1e5 + 5;
const LL INF = 1e14;
int n, m, op, par[N], d[N];
int h[N], e[N], ne[N], idx;
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
unordered_map cost, id;
LL f[N][N], g[N][N];
int pos[4][N][N];
vector path[N][N], pathp[N][N];
char c[N];
void dfs(int u)
{
for (int i = 0; i <= d[u]; i ++)f[u][i] = INF;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
d[v] = d[u] + 1;
dfs(v);
for (int j = 0; j <= d[u]; j ++)
{
g[u][j] = INF;
pos[0][u][j] = pos[1][u][j] = pos[2][u][j] = pos[3][u][j] = 0;
pathp[u][j].clear();
}
if (i == h[u])
{
for (int j = 1; j f[v][j])
{
g[u][j - 1] = f[v][j];
pos[0][u][j - 1] = v, pos[1][u][j - 1] = j;
}
}
}
else
{
for (int j = 0; j <= d[u]; j ++)
{
for (int k = 1; k f[u][j] + f[v][k])
{
g[u][max(j, k - 1)] = f[u][j] + f[v][k];
pos[0][u][max(j, k - 1)] = u, pos[1][u][max(j, k - 1)] = j;
pos[2][u][max(j, k - 1)] = v, pos[3][u][max(j, k - 1)] = k;
}
}
}
}
for (int j = 0; j <= d[u]; j ++)
{
if (pos[0][u][j])
{
for (auto item : path[pos[0][u][j]][pos[1][u][j]])pathp[u][j].push_back(item);
}
if (pos[2][u][j])
{
for (auto item : path[pos[2][u][j]][pos[3][u][j]])pathp[u][j].push_back(item);
}
}
for (int j = 0; j <= d[u]; j ++)
{
f[u][j] = g[u][j];
path[u][j] = pathp[u][j];
}
}
if (h[u] == -1)f[u][0] = 0;
int cur = u, pos = 0;
LL Min = f[u][0];
string str = "";
for (int i = 1; i Min)
{
f[u][i] = Min;
path[u][i] = path[u][pos];
}
else if (cost[str] && f[u][i] > Min + cost[str])
{
f[u][i] = Min + cost[str];
path[u][i] = path[u][pos];
path[u][i].push_back({id[str], {par[cur], u}});
}
if (Min > f[u][i])
{
Min = f[u][i];
pos = i;
}
cur = par[cur];
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> op;
c[1] = '#', cost["#"] = -1, d[1] = 1;
for (int i = 2; i > par[i] >> c[i];
add(par[i], i);
}
for (int i = 1; i > w >> str;
reverse(str.begin(), str.end());
if (!cost[str] || cost[str] > w)
{
cost[str] = w;
id[str] = i;
}
}
dfs(1);
if (f[1][0] >= INF)f[1][0] = -1;
cout << f[1][0] << '\n';
if (op && ~f[1][0])
{
cout << path[1][0].size() << '\n';
for (auto item : path[1][0])cout << item.y.x << ' ' << item.y.y << ' ' << item.x << '\n';
}
return 0;
}
然后发现博弈论是9级考点之后光速去复习别的去了。
CRT
不是那个CRT，那个 CRT 是 Chongqing Rail Transmit
推导主要运用同余方程可加性，将原有的方程拆成 n 组，每组 n 个。
记 N = \prod_{i = 1}^{n} b_i
对于一组方程
$x_k \equiv a_i (k = i)$
$x_k \equiv 0(k \neq i)$（有 $n – 1$ 个）
令 y_k = x_k \times a_k
由 n – 1 个方程可以得出 y_k \equiv 0 \pmod{\frac{N}{b_k}}，令 c_k = \frac{N}{b_k} 即有： y_k = c_k \times t_k
剩下的一个方程可以得出 y_k \equiv 1 \pmod{b_k}，带入有：
$c_k \times t_k \equiv 1 \pmod{b_k}$，$t_k$ 就是 $c_k$ 在 $mod$ $b_k$ 的乘法逆元。
同理，对于每一组，我们综合之后有： x = \sum_{i = 1}^{n} c_i \times t_i \times a_i，非常熟悉的柿子呢！
然后就没有然后了，exCRT 是 9级考点，而且本身和 CRT 基本没有半毛钱关系，撤！
并非例子的例子 P3868。
柿子很好推，推完之后就是 CRT 板子。
没啥用的代码：
#include
using namespace std;
const int N = 15;
// ax1 + by1 = 1
// bx2 + (a % b) y2 = 1
// ax1 + by1 = bx2 + (a % b)y2
// ax1 + by1 = bx2 + (a - (a / b) * b) y2
// ax1 + by1 = bx2 + ay2 - (a / b) * b * y2
// x1 = y2
// x2 - (a / b) * y2 = y1
typedef long long LL;
void exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
/*
b[i] | (n - a[i])
n - a[i] = 0 (mod bi)
n = a[i] (mod b[i])
*/
int n;
LL a[N], b[N];
int main()
{
scanf("%d", &n);
LL mul = 1;
for (int i = 1; i <= n; i ++)scanf("%lld", &a[i]);
for (int i = 1; i <= n; i ++)
{
scanf("%lld", &b[i]);
mul *= b[i];
}
__int128 res = 0;
for (int i = 1; i <= n; i ++)
{
LL c = mul / b[i];
LL k, t;
exgcd(c, b[i], k, t);
res += (__int128)c * (__int128)k * (__int128)a[i];
res = ((res % mul) + mul) % mul;
//c * x + b[i] * y = 0
}
LL r = ((res % mul) + mul) % mul;
printf("%lld", r);
return 0;
}
好充实对吧，还有更为充实的。
FHQ-TREAP 和 可持久化
不行了为什么我学的平衡树是带旋Treap 和 Splay 没有一个能持久化的。
那就学一下无旋Treap(FHQ-TREAP) 吧。
TREAP = BST(Binary Search Tree) + HEAP。
这个名字已经说清楚了它要做什么了：
- 对于每个节点给定的 val，满足 BST 的性质（左儿子的 val 一律小于等于根的 val，右儿子的 val 大于根的 val。
但是这点很容易导致一个致命的问题：最坏情况下树呈一个链结构，这就不用做了。
于是它还满足下面的性质：
- 对于每个节点一般为随机的 key，满足堆的性质。
接下来介绍 FHQ-TREAP 的主要操作: split 和 merge。
真是分久必合合久必分。
split 函数主要完成将一棵树按 val 分裂成两棵，其中保证一棵权值小于等于 val，另一棵全部大于 val
给出代码，原理很好理解，因为满足 BST 的性质，因此相当于判断当前节点是否小于等于 val，是则分裂右子树，否则分裂左子树。
$x, y$ 代表分裂结束后的两根。
void split(int u, int v, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
if (tr[u].val <= v)
{
x = u;
split(tr[x].r, v, tr[x].r, y);
}
else
{
y = u;
split(tr[y].l, v, x, tr[y].l);
}
pushup(u);
}
merge 操作，顾名思义，将两棵分裂的树合并起来，注意两棵树合并前要满足一棵树权值全部小于（等于）另一棵树。
给出代码，原理也很好理解，运用堆的性质。
int merge(int x, int y)
{
if (!x || !y)return x + y;
if (tr[x].key < tr[y].key)
{
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
}
else
{
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
然后是平衡树基本上都要有的操作：
插入：
把树按 v 分裂成两部分，在中间插入就是了。
void ins(int v)
{
int x, y, z;
split(root, v, x, z);
y = newnode(v);
root = merge(merge(x, y), z);
}
删除：
把树裂成三部分，中间部分只含 v，删掉就行了。
void del(int v)
{
int x, y, z;
split(root, v, x, z);
split(x, v - 1, x, y);
y = merge(tr[y].l, tr[y].r);
root = merge(merge(x, y), z);
}
求排名(get_rk)：
按 v – 1之后求一下size$ 就是。
注意 rank 不能全小写，本身是 C++ 的一个函数用于求数组维数。
int get_rk(int v)
{
int x, y;
split(root, v - 1, x, y);
int res = tr[x].Size + 1;
root = merge(x, y);
return res;
}
其余功能都是类似的，换言之只要知道怎么分裂就都能推出来。
注意分裂其实有两种方式，一种按 val，一种按 size，两者出现频率不相上下。
板子P6136
#include
using namespace std;
const int N = 2e6 + 5;
mt19937 rd(time(0));
struct node
{
int l, r;
int val, key, Size;
}tr[N];
int n, m, root, idx;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
int newnode(int v)
{
tr[++ idx] = {0, 0, v, (int)rd(), 1};
return idx;
}
void pushup(int u){tr[u].Size = tr[tr[u].l].Size + tr[tr[u].r].Size + 1;}
void split(int u, int v, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
if (tr[u].val <= v)
{
x = u;
split(tr[x].r, v, tr[x].r, y);
}
else
{
y = u;
split(tr[y].l, v, x, tr[y].l);
}
pushup(u);
}
int merge(int x, int y)
{
if (!x || !y)return x + y;
if (tr[x].key < tr[y].key)
{
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
}
else
{
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
void ins(int v)
{
int x, y, z;
split(root, v, x, z);
y = newnode(v);
root = merge(merge(x, y), z);
}
void del(int v)
{
int x, y, z;
split(root, v, x, z);
split(x, v - 1, x, y);
y = merge(tr[y].l, tr[y].r);
root = merge(merge(x, y), z);
}
int get_rk(int v)
{
int x, y;
split(root, v - 1, x, y);
int res = tr[x].Size + 1;
root = merge(x, y);
return res;
}
int get_kth_id(int u, int k)
{
if (k <= tr[tr[u].l].Size)return get_kth_id(tr[u].l, k);
else if(k == tr[tr[u].l].Size + 1)return u;
else return get_kth_id(tr[u].r, k - tr[tr[u].l].Size - 1);
}
int get_pre_id(int v)
{
int x, y;
split(root, v - 1, x, y);
int res = get_kth_id(x, tr[x].Size);
root = merge(x, y);
return res;
}
int get_suc_id(int v)
{
int x, y;
split(root, v, x, y);
int res = get_kth_id(y, 1);
root = merge(x, y);
return res;
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; i ++)
{
int x = read();
ins(x);
}
int lastans = 0, res = 0;
for (int i = 1; i <= m; i ++)
{
int op, v;
scanf("%d%d", &op, &v);
v ^= lastans;
if (op == 1)ins(v);
else if (op == 2)del(v);
else if (op == 3)res ^= (lastans = get_rk(v));
else if (op == 4)res ^= (lastans = tr[get_kth_id(root, v)].val);
else if (op == 5)res ^= (lastans = tr[get_pre_id(v)].val);
else if (op == 6)res ^= (lastans = tr[get_suc_id(v)].val);
}
printf("%d\n", res);
return 0;
}
优美的板子，比有旋Treap那家伙好多了！
可持久化：
我们在可持久化线段树一节中其实学到过类似的方法，考虑到Treap本身就是动态开点的(bushi)，因此实现方法是类似的：在需要修改的地方新加入节点。
可持久化往往对空间要求不会非常严格，因此请将大小变为 原来数据规模 << 7
板子P3835
#include
using namespace std;
const int N = 3e7 + 5;
const int INF = 2147483647;
mt19937 rd(time(0));
struct node
{
int l, r;
int val, key, Size;
}tr[N];
int n, m, idx, root[N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
int newnode(int v = 0)
{
tr[++ idx] = {0, 0, v, (int)rd(), 1};
return idx;
}
void pushup(int u){tr[u].Size = tr[tr[u].l].Size + tr[tr[u].r].Size + 1;}
void split(int u, int v, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
if (tr[u].val <= v)
{
x = newnode();
tr[x] = tr[u];
split(tr[x].r, v, tr[x].r, y);
pushup(x);
}
else
{
y = newnode();
tr[y] = tr[u];
split(tr[y].l, v, x, tr[y].l);
pushup(y);
}
}
int merge(int x, int y)
{
if (!x || !y)return x + y;
if (tr[x].key < tr[y].key)
{
int rt = newnode();
tr[rt] = tr[x];
tr[rt].r = merge(tr[rt].r, y);
pushup(rt);
return rt;
}
else
{
int rt = newnode();
tr[rt] = tr[y];
tr[rt].l = merge(x, tr[rt].l);
pushup(rt);
return rt;
}
}
int ins(int root, int v)
{
int x, y, z;
split(root, v, x, z);
y = newnode(v);
return merge(merge(x, y), z);
}
int del(int root, int v)
{
int x, y, z;
split(root, v, x, z);
split(x, v - 1, x, y);
if (y)y = merge(tr[y].l, tr[y].r);
return merge(merge(x, y), z);
}
int get_rk(int root, int v)
{
int x, y;
split(root, v - 1, x, y);
int res = tr[x].Size + 1;
merge(x, y);
return res;
}
int get_kth_id(int u, int k)
{
if (k <= tr[tr[u].l].Size)return get_kth_id(tr[u].l, k);
else if(k == tr[tr[u].l].Size + 1)return u;
else return get_kth_id(tr[u].r, k - tr[tr[u].l].Size - 1);
}
int get_pre_id(int root, int v)
{
int x, y;
split(root, v - 1, x, y);
int res = -INF;
if (x)res = get_kth_id(x, tr[x].Size);
merge(x, y);
return res;
}
int get_suc_id(int root, int v)
{
int x, y;
split(root, v, x, y);
int res = INF;
if (y)res = get_kth_id(y, 1);
merge(x, y);
return res;
}
int main()
{
n = read();
for (int i = 1; i <= n; i ++)
{
int ver = read(), op = read(), v = read();
root[i] = root[ver];
if (op == 1)root[i] = ins(root[i], v);
else if (op == 2)root[i] = del(root[i], v);
else if (op == 3)printf("%d\n", get_rk(root[i], v));
else if (op == 4)printf("%d\n", tr[get_kth_id(root[i], v)].val);
else if (op == 5)printf("%d\n", tr[get_pre_id(root[i], v)].val);
else if (op == 6)printf("%d\n", tr[get_suc_id(root[i], v)].val);
}
return 0;
}
区间操作（以反转为例子）：
考虑 Treap 本身性质满足 BST 的性质，因此如果交换一个点上的 左右儿子，实际上整个序列就反过来了！
注意这里 split 所用的就是按照 size 分裂而不是 val，显然交换后 val 并不满足 BST 性质。
这样一个一个下去做还是太慢了，考虑能不能延迟这个过程，有需要再做。
没想到吧哈哈哈甚至Treap也是有懒标记的，简直就是线段树。
pushdown 和动态开点线段树/可持久化线段树完全一样，不放了。
最后放一下可持久化加上带懒标记的 P5055
#include
using namespace std;
const int N = 2e5 + 5;
mt19937 rd(time(0));
typedef long long LL;
struct node
{
int l, r;
LL val, sum;
int tag, key, Size;
}tr[N << 7];
int n, m, idx, root[N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
int newnode(int v = 0)
{
tr[++ idx] = {0, 0, v, v, 0, (int)rd(), 1};
return idx;
}
int copy(int u)
{
int pos = newnode();
tr[pos] = tr[u];
return pos;
}
void pushup(int u)
{
tr[u].Size = tr[tr[u].l].Size + tr[tr[u].r].Size + 1;
tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum + tr[u].val;
}
void pushdown(int u)
{
if (!tr[u].tag)return;
if (tr[u].l)tr[u].l = copy(tr[u].l);
if (tr[u].r)tr[u].r = copy(tr[u].r);
swap(tr[u].l, tr[u].r);
if (tr[u].l)tr[tr[u].l].tag ^= 1;
if (tr[u].r)tr[tr[u].r].tag ^= 1;
tr[u].tag = 0;
}
void split(int u, int v, int &x, int &y)
{
if (!u)
{
x = y = 0;
return;
}
pushdown(u);
if (tr[tr[u].l].Size + 1 <= v)
{
x = copy(u);
split(tr[x].r, v - tr[tr[u].l].Size - 1, tr[x].r, y);
pushup(x);
}
else
{
y = copy(u);
split(tr[y].l, v, x, tr[y].l);
pushup(y);
}
}
int merge(int x, int y)
{
if (!x || !y)return x + y;
pushdown(x), pushdown(y);
if (tr[x].key < tr[y].key)
{
int rt = copy(x);
tr[rt].r = merge(tr[rt].r, y);
pushup(rt);
return rt;
}
else
{
int rt = copy(y);
tr[rt].l = merge(x, tr[rt].l);
pushup(rt);
return rt;
}
}
int main()
{
n = read();
LL lastans = 0;
for (int i = 1; i <= n; i ++)
{
int ver = read(), op = read();
root[i] = root[ver];
if (op == 1)
{
int pos = read(), x, z;
LL v = read();
pos ^= lastans, v ^= lastans;
split(root[i], pos, x, z);
root[i] = merge(merge(x, newnode(v)), z);
}
else if (op == 2)
{
int pos = read(), x, y, z;
pos ^= lastans;
split(root[i], pos, y, z);
split(y, pos - 1, x, y);
root[i] = merge(x, z);
}
else if (op == 3)
{
int l = read(), r = read(), x, y, z;
l ^= lastans, r ^= lastans;
split(root[i], r, y, z);
split(y, l - 1, x, y);
tr[y].tag ^= 1;
root[i] = merge(merge(x, y), z);
}
else if (op == 4)
{
int l = read(), r = read(), x, y, z;
l ^= lastans, r ^= lastans;
split(root[i], r, y, z);
split(y, l - 1, x, y);
printf("%lld\n", lastans = tr[y].sum);
root[i] = merge(merge(x, y), z);
}
}
return 0;
}
过于充实的一天甚至有点过饱和了。