目前 4/6/12 (code/sol/problem)
D1T1 Two Currencies
给定一棵大小为 \(n\) 的树 \(T\)，树上有 \(m\) 条关键边，经过关键边要么缴纳一枚金币要么缴纳 \(c\) 枚银币。
有 \(Q\) 组询问，每次询问从 \(a\) 走到 \(b\) 带 \(x\) 枚金币 \(y\) 枚银币能否到达，如果可以到达还需最大化剩下的金币数。
\(n,m,Q\le 10^5\)。
使用可持久化线段树记录下每个点向上到根的边权，那么 \(a\to b\) 可以用三棵线段树做差得到。
我们希望金币最多，那么希望银币带走尽可能多的关键边，于是二分查一下能够处理掉多少关键边就行了。
时间复杂度线性对数。
D1T2 Festivals in JOI Kingdom 2
称 \(n\) 个区间组成的区间组 \([a_i,b_i]\) 是好的，当且仅当：
\(1\sim 2n\) 在 \(a,b\) 中各只出现一次。
\(a_i<b_i\)，\(a_i<a_{i+1}\)。
下列算法计算「选出尽可能多的区间它们两两之间无交」的答案错误：
- 按顺序扫描区间，如果当前区间与之前选择的区间均无交，则将其加入答案。
对好的区间组计数，\(n\le 2\times 10^4\)。
不会。
如果暴力枚举括号序列，然后再枚举每一个左括号的归属的话，可以拿 \(10\) 分。
D1T3 Passport
有 \(n\) 个点，初始时只能访问某一个点，在 \(i\) 可以花费一的代价使得你可以访问 \([L_i,R_i]\) 这些点，满足 \(L_i\le i\le R_i\)。
\(q\) 次询问，每次询问从某一个点出发，最少需要花费多少代价可以访问所有点。
\(n\le 2\times 10^5\)。
对每个点建虚点表示买不买票，那么可以得到一种做法是原本的点连向虚点，这个边有代价，然后虚点再向对应区间的原点连边。
「向区间连边」，可以想到线段树优化建图，访问所有点，其实只要访问 \(1\) 和 \(n\) 就行了。
建反图从 \(1\) 和 \(n\) 分别跑最短路，那么可以得到初始答案 \(d_{1,u}+d_{u,n}\)，注意到两边方案可能有重边，对重边的处理类似三角不等式 \(d_{u}+w<d_v\)，再跑一遍最短路就行了。
时间复杂度线性对数平方，实现的不好可能会被卡常。
D2T1 Belt Conveyor
交互题，给定一棵 \(n\) 个点的树，边有方向，但是不知道方向。
每一次询问，你可以指定一个边集和一个点集，翻转边集的所有边之后，将你指定的点集中的点上各放置一个棋子，将棋子向任意一条所在点的出边移动一步，返回有棋子的点，并将树还原。
在 \(30\) 步内确定边的方向，\(n=10^5\)，交互库自适应。
所有的一度点可以同时确定，所有的二度点可以同时三步确定。
那么同时确定所有一度点和二度点之后，可以将他们删除，然后确定新的一度点和二度点。
很难卡，估计卡不到 \(30\) 步。
另一种做法是，按 \(dep\bmod 3\) 分组，每次选最大的一组来确定一条边，当一个点的所有边都被确定就把它删掉。
这样做是 \(\log _{1.5} n=29\) 次，是标算。
写点实现细节：上述做法会出现两个点的祖先被走到，但是一个点其实是走到儿子的情况，实现中，可以先写点的边均为出边，然后写走到儿子，最后讨论祖先，这样就可以规避了，样例很强。
D2T2 Council
给定一个 \(n\) 行 \(m\) 列的 \(01\) 矩阵 \(a\)，先删去其中的第 \(x\) 行，然后你再选择删除一行，最大化剩下的 \(n-2\) 行 \(m\) 列矩阵中 \(\sum_{j=1}^m [\sum_{i=1}^{n-2}a_{i,j}\ge \lfloor\frac n2\rfloor\ ]\)。
对 \(x\in[1,n]\) 求解，\(n\le 3\times 10^5\)，\(m\le 20\)。
对于每一个 \(a_i\)，考虑求出一个 \(b_i\)，满足删除 \(i\) 之后个数恰好为 \(\lfloor\frac n2\rfloor\) 的列的集合。
如果删掉的另一行是 \(1\)，那么这个就不会被通过，所以也就是对于每个 \(i\) 找出一个 \(j\) 满足 \(\text{popcount}(b_i\And a_j)\) 尽可能小，\(a_j\) 取反之后就是取最大值，满足 \(i\not= j\)。
首先求出 \(f_S\) 表示对于某一个 \(S\) 是否存在 \(S\subset a_j\)，这个可以高维后缀和，然后求出 \(g_{i,S}\) 表示是否存在 \(S\) 的子集满足 popcount 为 \(i\)，这个可以高维前缀和。
注意到满足 \(i\not= j\)，记一下每一个 \(1\) 来自哪里就行了，记两个本质不同的。
D2T3 Mizuyokan 2
给定一个长为 \(n\) 的序列 \(d\)，支持如下操作：
单点修改。
区间查询，对于区间 \([l,r]\)，最少需要如下操作几步，可以得到一个 zigzag 序列：
操作：选择 \(i\)，删除 \(d_i,d_{i+1}\)，在 \(i\) 这个位置插入 \(d_i+d_{i+1}\)。
zigzag 序列：升降相间的序列。
上述操作的出现情况一定是先修改一次再查询一次，如此反复。
\(n\le 2.5\times 10^5\)，\(5\times 10^4\) 次修改查询。
D3T1 Chorus
给定一个长为 \(2n\) 的 \(01\) 串，有 \(n\) 个 \(0\)，\(n\) 个 \(1\)，你需要将他们划分成 \(k\) 个子序列，且 \(k\) 个子序列均可以划分成长度相等，先是均为 \(0\) 再是均为 \(1\) 的两个子段。
当然有的时候这不可行，你可以交换相邻的字符，在最小步数内使得存在一种划分方案。
\(n\le 10^6\)。
D3T2 Cookies
有 \(n\) 种物品，每种物品有 \(a_i\) 个，你要把他们都装进盒子里，满足：
盒子里的物品各不相同。
盒子里的物品个数必须属于一个集合 \(b\)。
求一组方案，如果存在多种，求出盒子最少的一种方案。
\(|b|\le n\le 1.5\times 10^4\)，\(\sum a_i\le 1.5\times 10^4\)。
D3T3 Tourism
区间询问虚树所占连通块的大小。
\(n\le 10^5\)。
一个普通的想法是莫队，每次暴力用 set 查 dfn 的前驱后继，然后统计答案，这个是 \(O(n\sqrt{n} \log n)\) 的，不能过。
如果改成回滚莫队即只删不加，用链表维护 dfn 的前驱后继，就可以做到 \(O(n\sqrt{n})\)，应该能过。
考虑猫树分治，对于关键点来处理，对于每一层，对 \([l,r]\) 建虚树，我们希望求出跨越 \(mid\) 的答案：
-
将点划分成两类 \([l,mid]\) 和 \([mid+1,r]\)，下文将这两类点叫做一类二类。
-
考虑一条虚树上的边，它将虚树分为了两个连通块 \(S_1,S_2\)，他的边权为 \(w\)，那么，\(w\) 会被算入贡献的询问有：
-
注意到 \(mid\) 和 \(mid+1\) 一定得在 \(w\) 的一边，否则这条边一定会被计入答案。
-
设在的那一边为 \(S_1\)，另一边是 \(S_2\)，那么记 \(S_2\) 中最大的一类点是 \(u\)，最小的二类点是 \(v\)，那么类似 \(l'\le u\lor r'\ge v\) 会被加上 \(w\)，可以拆成 \(l'\le u\)，\(r'\ge v\)，\(l'\le u\land r'\ge v\) 容斥。
-
-
上述三种询问均可以使用 \(l'\in[L_1,R_1],r'\in[L_2,R_2]\) 的形式描述，是二维数点，扫描线树状数组即可。
每次分治的时间复杂度是 \(O(L\log L)\) 的，所以总时间复杂度是 \(O(n\log n)\) 的。
D4T1 The Last Battle
通信题，小 A 和小 B 利用一个 \(8\times 8\) 的格子通信，小 A 可以向格子里除了第 \(x\) 行和第 \(y\) 列的数填上 \(01\)，第 \(x\) 行和第 \(y\) 列将由交互库填上，小 A 需要传递给小 B 一个长度为 \(n\) 的 \(01\) 串，小 B 只知道 \(n\) 和这个 \(8\times 8\) 的格子。
正确传输 \(n=43\) 的串。
D4T2 Security Guard
不写了，鸽。
D4T3 Bitaro's travel
以前这里有题意的，但是被不小心删了，所以鸽了。
绝对值的 beat，有意思，注意到反方向的一方距离一定会翻倍，所以转向走不超过 \(\log V\) 次。
假设现在访问了 \([l,r]\)，在 \(u\)，那么转移也就是比较 \(u-x_{l-1}\) 和 \(x_{r+1}-u\)，我们希望求出一直走的终止点，以向左为例就是找到 \(i\) 满足 \(x_i-x_{i-1}<x_{r+1}-x_i\)，是一个偏序问题，在线回答偏序问题选择主席树，从而在 \(O(n\log V\log n)\) 的时间复杂度内解决。
标签：10,le,记录,可以,mid,times,JOISC,2023,区间 From： https://www.cnblogs.com/cnyzz/p/17252198.html