NOI模拟赛题整理-拓冰建站

时间从近往远吧。

代码源 day2

T1

这是一道交互题。

交互库中隐藏了一个大小为 \(n\) 的简单无向图 \(G = (V, E)\)，其中节点编号为 \(1 \sim n\)。你需要通过有限次询问来确定这个无向图的所有边。

你可以向交互库询问一个 \(1 \sim n\) 的排列 \(p = [p_1, p_2, \dots, p_n]\)。对于每次询问，交互库会返回一个长度为 \(n\) 的 01 序列 \(R = [r_1, r_2, \dots, r_n]\)。其中对于每一个 \(i\)（\(1 \leq i \leq n\)），\(r_i\) 表示在排列 \(p\) 中，节点 \(p_i\) 与所有排在它前面的节点（即 \(p_1, p_2, \dots, p_{i-1}\)）之间的边数的奇偶性。

形式化地，返回值序列中第 \(i\) 个元素 \(r_i\) 的计算公式为：

\[r_i = \left( \sum_{j=1}^{i-1} \left[ \{p_i, p_j\} \in E \right] \right) \bmod 2 \]
其中，若条件为真，则 \([\text{条件}] = 1\)，否则为 \(0\)。特别地，当 \(i = 1\) 时，\(r_1 = 0\) 恒成立。

询问次数不超过 \(\lfloor\frac{n}{2}\rfloor+1\) ，还原出图 \(G\) 的所有边。

显然这是理论下界。

记 \(k=\lfloor\frac{n}{2}\rfloor+1\)。

重要的变量化视角，我们需要找到一个构造 \(k\) 个排列的方法，使得得到的 \((n-1)k\) 个方程消元后的秩是 \(\frac{n(n-1)}{2}\) 的。

显然奇数更强。

有若干方法，这里记录一个最有启发性的。

完全图分解哈密顿路的 Walecki 构造。

构造 \(P_i=[i,i-1,i+1,i-2,i+2\dots]\)（均在 \(\mod n\) 意义下）。

前 \(k\) 个排列已经满秩，可以刻画所有信息了。

写出方程可以手动高消。

不会手动高消咋办？

考虑对每个值 \(v\)，在 \(k\) 个排列中得到的以它为靠后元素的变量组成的 \(k\) 个方程，做局部高斯消元，可以做 \(O(n\times \frac{n^3}{w})\)。

此时变量非常分散吗，我们只需要用 \(BFS\) 逐点更新即可。

（即每次取出一个确定变量，到包含这个变量的 \(O(nk)\) 个方程里消去这个变量的影响）

T2

神秘分块题目，还是能会一点东西的。

给出一个初始全 0 的大小为 \(N \times N\) 的矩阵 \(A\)，长度为 \(N\) 的排列 \(P\)，以及 \(M_1\) 次修改操作，\(M_2\) 次询问操作。

每次修改操作给出 \(L_1, R_1, L_2, R_2, x\)，表示将所有满足 \(L_1 \leq P_i \leq R_1\) 且 \(L_2 \leq j \leq R_2\) 的 \(A_{i,j}\) 加上 \(x\)。

每次询问操作给出 \(L_1, R_1, L_2, R_2\)，你需要求出

\[\max_{L_1 \leq i \leq R_1,\ L_2 \leq j \leq R_2} A_{i,j} \]
的值。

注意，所有询问操作在修改操作之后。

记 \(C=M_1,Q=M_2\)。

平面问题进行分块的常见方法：

按修改量对一维分块，每块里只有 \(\sqrt C\) 的散块修改量，因此可以分为 \(\sqrt{C}\times \sqrt{C}\) 个小矩形，行数和列数都是 \(\sqrt C\) 级别。

分块方法：用数组 \(c\) 记录对这一维的修改的所有 \(l,r\) 的出现次数，即 \(c_l,c_r\) 都加上 \(1\)。

我们要求分块，使得块内区间的 \(c\) 总和是 \(O(\sqrt C)\) 级的，这里可以双指针。

出现单个 \(c_i>\sqrt C\) ，需要对该行单独分出进行处理。

这样最多划分出 \(3\sqrt C\) 个块。同时每个块内可以被划分为 \(O(\sqrt C\times \sqrt C)\) 的小网格，每个网格内部值相同。对于单个 \(c_i>\sqrt C\) 的，如果假定 \(C,N\) 同阶也是一样的。
想办法 \(O(n\times t)-O(1\times t)\) 处理过整块的单次询问。

一共有 \(O(Q\sqrt C)\) 次询问。
对块内划分 \(\sqrt C\times \sqrt C\) 的小网格，对修改做二维前缀和等操作快速处理出每个小网格的值。

最多有 \(O(Q)\) 次散块查询，可以遍历所有行，想办法对列做 \(O(\sqrt C)-O(1)\) 预处理-查询操作。

在本题中，由于列上查询和修改都是区间，所以按列分块。

直接在标准 \(1\sim n\) 上做行修改，查询的时候按照变成查 \(P^{-1}_i\in [L_1,R_1]\) 的行。

接着，切分出小矩形，块内修改做二维前缀和处理修改，对于跨整块的修改就直接打一个一维差分标记（注意这个修改过整块，因此是在 \(1\times n\) 的维度上的）。

对于整块查询，先做一些预处理：
- 首先处理出所有整块修改的差分标记，这是 \(O(n)\) 的。
  
  其次借助二维前缀和后做出的的每个行最值，用双指针映射到 \(1\times n\) 这一维度上。
  
  这样就能处理出 \(n\) 行每一行的最值了。
  
  再按照 \(P^{-1}\) 重排行最值，并借助压位 ST 表建立 \(O(n)-O(1) RMQ\)。
  
  就可以 \(O(1)\) 回答询问了。
对于散块查询。

对于 \(\sqrt C\times \sqrt C\) 的小矩形。

首先，对于查询，离散化出对于这 \(\sqrt C\) 列的查询的左右端点。

这里是一个排序和离散化的复杂度，所有块总和 \(O(Q\log n)\)。

枚举 \(\sqrt C\) 行等价类 \([ql,qr]\)。

对于每一行，我们要查询什么？

需要查询 \(P^{-1}_x\in [L_1,R_1],x\in [ql,qr]\) 的行中，在 \([L_2,R_2]\) 的列的最值。

可以注意到，这里维度已经解耦了。

我们只需要查询整块修改造成的 \(P^{-1}_x\in [L_1,R_1],x\in [ql,qr]\) 的行最值。

以及这个在范围内的散块修改造成的列最值（因为我们枚举了行等价类 \([ql,qr]\)，因此拆分贡献后最优行和最优列是分开的）。

按 \(P^{-1}_{ql}\sim P_{qr}^{-1}\) 进行排序后建立 \(O(n)-O(1) RMQ\)，排序可以整体 \(O(n)\) 将所有块都排了。

同时对 \(\sqrt C\) 列也建立 \(O(n)-O(1) RMQ\)。

然后对所有询问，预先排序 \(L_1,R_1\)，在这里双指针得到 \(L_1,R_1\) 在这里对应的区间。\(L_2,R_2\) 对应的区间早已在枚举 \([ql,qr]\) 之前已经得到。

现在就只需要 \(2\) 个 RMQ 查询了。

code

代码源 Day1

区。

T1

有 \(n\) 盏路灯它们的坐标为 \((1, h_1), \dots, (n, h_n)\)，其中 \(h_i\) 是一个 \(1\) 到 \(n\) 的排列。

每盏灯会随机选择往左照或者往右照。

如果 \(i\) 这盏灯往左照，它会照亮 \(0 \leq x \leq i, \ 0 \leq y \leq h_i\) 这个矩形区域。

如果 \(i\) 这盏灯往右照，它会照亮 \(i \leq x \leq n+1, \ 0 \leq y \leq h_i\) 这个矩形区域。

记 \(S\) 表示这些灯照亮的区域的面积的并，请输出 \(2^S\) 的期望，对 \(998244353\) 取模的结果。

建立笛卡尔树，状态就设为当前没点亮的区间只剩下这一个且处理高度已经到这个点的高度的概率。

枚举往左往右好转移给儿子。贡献计算是一个高度逐衰的东西，可以矩阵快速幂加速。

T2

~~会所有部分分不会正解且知道所有性质怎么办~~

你有一个双端队列。你要进行 \(n\) 个操作：

\(0\) x，往队列开头插入一个数字 \(x\)。

\(1\) x，往队列末尾插入一个数字 \(x\)。

同时双端队列的容量是 \(K\)。

一旦当队列的大小超过 \(K\)，你会移除队列中的最小元素，如果有多个相同的最小元素，那么会删除最靠近开头的 \(K\) 个。假设第 \(i\) 次操作之后，队列的开头元素为 \(f_{K,i}\)。

你想知道队列开头的元素变化量是多大，即

\[g(K) = \sum_{i=1}^{n-1} |f_{K,i} - f_{K,i+1}| \]
请对 \(K = 1, 2, \dots, n\) 回答这个问题。

需要找到一种方法整体刻画所有容量的开头元素。

显然我们可以做一点预处理，给每个元素赋一个位置，那么比较元素大小可以看作先比较值，再比较位置值吗，现在我们确定了所有元素的顺序。

不妨设值为 \(a_i\)（已经是双关键字过的值，可以直接比较），位置为 \(b_i\)。

有若干观察，比如尾插不会使得开头元素变小，所以全尾插的特殊性质只需要计算 \(f_{n,i}-f_{1,i}\) 了，这显然是容易的。

当时就被这个性质困死了，即使我知道更加关键的性质。

Key Obversion:\(f_{k,i}\)是元素 \(1\sim i\) 中 \(a\) 前 \(k\) 大元素里 \(b\) 最小的一个。

其实这个性质就可以刻画所有的开头元素了。

将元素 \(1\sim i\) 按照 \(a\) 从大到小排序，并取 \(b\) 的前缀最小值位置 \(p_1\sim p_m\)。

则 \(f_{[p_x,p_{x+1}-1],i}\) 的值就是 \(a_{p_x}\)。

这里有一个小转化，但是我没想到，于是得到了关键性质也没做出来。

考虑逐个加入元素并维护答案和序列 \(p\)。

答案计算的一个比较简单的形式是：

\[ans_k=f_{k,n}-f_{k,1}+2\sum_{f_{k,i+1}<f_{k,i}}f_{k,i+1}-f_{k,i} \]

考虑加入一个元素，用树状数组来维护排名的查询，用双端队列维护 \(p\)。

如果是插尾，除非它的 \(a\) 是最值，否则不可能加入 \(p\)，如果是，将其加入 \(p\) 的开头。

这里不会引起任何元素值的下降，故无需统计。

如果是插头，它的 \(b\) 必然是当前的最小值，即前缀最小的，我们需要删去 \(p\) 尾部中 \(a\) 比它小的元素。

对于被删去部分，其 \(a\) 都会变大，也无需统计。

只有删完后，当前 \(p\) 中的 \(pre\) 元素，和删之前这个元素的后面元素 \(suf\)。

在没有加入这个元素时，\([pos_{pre},pos_{suf}-1]\) 的值都是 \(pre\)，但加入这个元素后，\([pos_{now},pos_{suf}-1]\) 变成了 \(now\)，产生了下降。

注意这个 \(pos_{suf}\) 是没加入 \(now\) 之前的排名。

这里用一个差分统计一下即可。

最后小常数 \(\log\) 解决了此问题。

T3

给你一个 \(n \times m\) 的矩阵，其中 \(a_{i,j}\)（\(1 \leq i \leq n\)，\(1 \leq j \leq m\)）表示第 \(i\) 行 \(j\) 列的字符。你要给每个位置填入一个字符满足：

每个字符是 A、B、C 中的一种。

任意 \(2 \times 2\) 的子矩阵必须包含三种不同的字符。

任意两个对角相邻的格子必须包含不同的字符。

同时还有 \(K\) 个限制。每个限制会给你两个相邻（这里相邻指有一条公共边）的格子 \((x_{i1}, y_{i1})\)、\((x_{i2}, y_{i2})\)，然后一个参数 \(a_i\)。如果你在这两个格子里面填入了相同的字符，那么你可以获得 \(a_i\) 的分数。

问你最多能获得多少分数，并且给出一组构造方案。

感觉是不知道的经典问题。

注意区分格子和格点

考虑这样的限制，本质上是在说任意一个 \(2\times 2\) 网格的 \(3\times 3\) 个格点，有且只有中心格点与上下左右四个方向的格点组成的四条边里选且只选一条，使得公用这条边的两个格子颜色相同。

这显然是个必要条件：将 \(n\times m\) 网格的 \((n+1)\times (m+1)\) 个点，将内部 \((n-1)\times (m-1)\) 个格点与所有的 \((n+1)\times (m+1)\) 进行匹配，使得内部格点全部参与匹配，且不存在外部格点与外部格点的匹配的最大权匹配方案。

后面会给出构造的充分性证明。

网络流建模是容易的，显然根据格点坐标和的奇偶性可以得到这是一个二分图。

将有边的格点（且端点至少有一个是内部格点）进行建边，题目给出的限制本质上是在加边权。
对于内部格点必须选这个限制，等价于源点汇点与内部格点连边，有正收益 \(\inf\)。（实现细节：费用流里标记的 \(INF\) 需要远大于这个 \(\inf\)）

跑网络流做最大权匹配，一旦当前增广路权值为负就退出。

根据网络流的割边，还原出匹配方案。

给出构造：

设格子 \((x,y)\)，其到格子 \((x+1,y)\) 的权值是 \(1+((x+y)\&1)\)，到 \((x,y+1)\) 的权值是 \(1+((x+y+1)\&1)\).

然后，将匹配边所对应的两个格子之间的权值设为 \(0\)，最后一个格子的权值定义为 \((0,0)\) 到这个格子的路径权值。

根据匹配的性质，容易证明任意路径权值相同，且任意 \(2\times 2\) 网格拥有三个颜色。

CQBZ Round 35

T1

有一个长度为 \(n\) 的合法括号序列 \(S\)，bot 可以在括号序列上行走。具体地，若 bot 在位置 \(i\)，则 bot 可以做如下操作之一：

若 \(i > 1\)，则可以消耗 \(1\) 点体力移动到 \(i-1\)；

若 \(i < n\)，则可以消耗 \(1\) 点体力移动到 \(i+1\)；

设 \(j\) 是与 \(i\) 匹配的括号位置，则可以移动到 \(j\) 且不消耗体力。

一组括号 \(i, j\)（\(i < j\)）匹配当且仅当：\(S_i = \texttt{(}\)，\(S_j = \texttt{)}\)，并且满足 \(i+1 = j\) 或者子串 \(S[i+1:j-1]\) 也是合法括号序列。

现在 bot 给你 \(q\) 次询问，每次给定两个整数 \(s, t\)，你需要求出 bot 从 \(s\) 移动到 \(t\) 最少需要多少体力。

显然建树，在没到同父亲之前，都是往父亲走更优，最后分讨一下是从父亲中转还是直接从儿子这边走。

T2

bot 有一棵 \(n\) 个结点的有根树，根结点为 \(1\)，树上每条边长度为 \(1\)，每个点初始有黑白灰三种颜色之一。

bot 会将所有灰色点染成黑白两种颜色之一，对于一种染色方案，bot 定义其价值如下：

bot 会选择树上若干条可经过重复点的路径，保证每条路径的起点都为根结点。

定义一种选择方案合法，当且仅当树上的每一个黑点都在至少一条路径上。

价值即为所有路径选择方案中，路径长度之和的最小值。

bot 想知道，若等概率随机给每个灰点染色，则价值的期望为多少。你只需要告诉 bot 答案对 \(10^9 + 9\) 取模后的结果即可。

正解是长剖，但我爆了。

考虑一个局面的贪心策略就是，合并两条链时，必然先走短链再走长链。

在合并点在短链的下半部分时就是优的，且这个贡献只与短链自己有关。

合并后就可以当作短链没了只剩下长链了。

越往上越好，因此子树内往上传的链只会有最深链一条，传两条不如内部先合并，如果内部都合并不了就不可能合并了。

研究一下这个模式，事实上可以直接获得一个局面的答案。

考虑将边 \((x,fa_x)\) 的权值设置为 \([mxd_x\le 2dep_x]+[mxd_x\le 2dep_x+1]\)。

\(dep\) 是深度，\(dep_{root}=0\)，\(mxd\) 是最深黑点深度。

可以讨论一下几条链的情况，它都可以正确计算贡献。即两条链的合并处在短链上半段，两条链的代价都计算完毕了，如果在下半段，那么会给出正确的贡献，可以将给出的 \(2\times edge\) 看作折返费用之类的。

链更多的情况证明是类似的。

有这个操作的话，我们只需要差分一下 \(dep\ge 2dep_x,dep\ge 2dep_x+1\) 的子树内灰/黑点个数，就可以算出每条边的总代价了。

代码非常好写。

#include<bits/stdc++.h>
using namespace std;
#define N 1050500
#define int long long 
const int p=1e9+9,i2=p+1>>1;
vector<int>e[N];
int ans,n,m,col[N],all,pw[N],dep[N],sta[N],top;
int c[N][3][3];
void dfs(int u,int fa){dep[u]=dep[fa]+1;sta[++top]=u;c[u][0][col[u]]++;if(u>1){int x=sta[top+1>>1],y=sta[top>>1];c[x][1][col[u]]++;if(top>1)c[y][2][col[u]]++;}for(auto v:e[u])if(v!=fa){dfs(v,u);for(int i:{0,1,2})for(int j:{0,1,2})c[u][i][j]+=c[v][i][j];}if(u>1){int a=c[u][0][2]?1:p+1-pw[c[u][0][0]];int b=c[u][1][2]?1:p+1-pw[c[u][1][0]];int d=c[u][2][2]?1:p+1-pw[c[u][2][0]];ans+=a+a+p-b+p-d;}--top;
}
signed main(){freopen("route.in","r",stdin);freopen("route.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;pw[0]=1;for(int i=1;i<=n;++i)pw[i]=pw[i-1]*i2%p;for(int i=1;i<=n;++i)cin>>col[i],++col[i];for(int i=1,u,v;i<n;++i)cin>>u>>v,e[u].push_back(v),e[v].push_back(u);top=-1;dfs(1,0);cout<<(ans%p+p)%p<<"\n";
}

T3

其实算比较套路的题？

bot 有一个 \(n \times m\) 的矩阵，其中第 \(i\) 行第 \(j\) 列上写着数字 \((p + i)^{q + j}\)，这里行和列均从 \(0\) 开始编号。

bot 想知道矩阵内不同数字的数量，你需要告诉他这个数对 \(998244353\) 取模的值。

\(n,m,p,q\le 10^{18}\)

其实就是 \([l_1,r_1]\) 的数字，各自的 \([l_2,r_2]\) 次方组成的数字个数。

显然的转化是考虑每个数字 \(x\le r_2\)，不存在 \(a\neq x,y\in Z,a^y=x\)。

它的幂次在 \([l_1,r_1]\) 中有 \([cl,cr]\) 是出现了，那么问题就转化为了统计 \([cl,cr],[l_2,r_2]\) 两两相乘后的不同数字个数。

又有 \(cr\le \log r_2\)，因此我们问题实际上分为两个部分：

找出所有的 \([cl,cr]\) 有多少个数字合法。
对一个 \([cl,cr]\) 算出答案。

先来解决前半部分，可以通过二分和幂次算出 \([cl,cr]\) 对应的数字范围 \([l,r]\) 使得 \(r^{cr}\le r_1,l^{cl}\ge l_1\)。

注意这里求出的数字范围只满足了数字 \(i,i^{cr}\le r_1,i^{cl}\ge l_1\)，所以最后还得做一个二维差分来容斥。

然后再算出区间中有多少个数字 \(x\) 是合法的，转化为前缀和，问题变为给定 \(n\)，求 \([2,n]\) 有多少合法数字。

其本质是在对唯一分解后的质因子指数 \(\gcd\) 做容斥。

设 \(f(i)\) 为 \(\le\) 的质因子指数 \(\gcd\) 为 \(i\) 的方案数，\(g\) 为指数 \(\gcd\) 是 \(i\) 倍数的方案数。

\[g(i)=\sum f(id)\implies f(i)=\sum g(id)\mu (d) \]
即：

\[f(1)=\sum \mu(d)g(d)=\sum \mu (d)(\lfloor\sqrt[d]{n}\rfloor-1) \]

再考虑如何计算 \([l,r]\times [l_2,r_2]\) 的不同数字个数。

\([l,r]\times [l_2,r_2]=\{x|\exists i\in [l,r],i|x\ \text{and}\ x\in [i\times l_2,i\times r_2]\}\)

考虑将 \(x\) 按照第二个条件分类，即将所有的 \(i\times l_2-1,i\times r_2\) 作为区间端点拿出来排序，得到的每个小区间中的 \(x\)，就有所有的 \(i\) 能否取的结果是一样的。

一个小区间要合法，怎么做呢？其实可以做覆盖的差分标记，即一个左端点给 \(1\)，一个右端点给 \(-1\)，若一个 \((s,t]\) 叠加 \(\le s\) 的差分标记后为正就是被需要的。

由此就可以拿出合法的 \(i\) 的范围 \([tl,tr]\)，这个限制条件就去掉了，转化为统计区间 \((s,t]\) 中有多少个数字，至少有一个 \([tl,tr]\) 的约数。

这很容易了，考虑大力容斥原理，用总的减去一个都没有的，有：

\[(t-s)-\sum_{S\subseteq\{tl,tl+1\dots tr\}}(-1)^{|S|}(\lfloor\frac{t}{\operatorname{lcm(S)}}\rfloor-\lfloor\frac{s}{\operatorname{lcm(S)}}\rfloor) \]

以 \(\operatorname{lcm}\) 分状态，其实不多，\(10^{18}\) 也就只有一百多万个。到这里已经可以跑过 \(10^{12}\) 了（只有几万个状态）。

如何加速呢？由于外部有 \(\log^2\) 的枚举，内层几十万的状态就已经很给压力了。

考虑，\(>\frac{tr}{2}\) 的质数是很垃圾的，选它和不选它直接导致状态数是否 \(\times 2\)。

考虑拿出一部分 \(>30\) 的质数来最后处理。

即，去掉这些个质数之后，将每个 \(\operatorname{lcm}(S)\) 对应的所有系数先存下来，以及它还能用这些个特殊质数的哪些部分也存下来。

考虑一下贡献怎么算，用底运算性质拆一下，对于需要使用特殊质数集合 \(S\)，其中元素分别为 \(v_0\sim v_{|S|-1}\)，对于一个系数为 \(c\) 且对应值为 \(\lfloor\frac{v}{\operatorname{lcm(S')}}\rfloor\) 为 \(K\)，其算出的答案为：

\[c\sum_{T\subseteq S}(-1)^T\lfloor\frac{K}{\operatorname{ \operatorname{mul}(T)}}\rfloor \]

如何快速计算？
不妨考虑对 \(K\) 做分解，设 \(val=\operatorname{mul}(S)\)，设 \(K=q\times val+r\)。

则拆分为：

\[ &c\sum_{T\subseteq S}(-1)^T\lfloor\frac{q\times val+r}{\operatorname{ \operatorname{mul}(T)}}\rfloor\\ =&c\sum_{T\subseteq S}(-1)^T(q\times \operatorname{mul}(S/T)+\lfloor\frac{r}{\operatorname{ \operatorname{mul}(T)}}\rfloor) \]

两边拆分开，可以迅速 \(O(1)\) 算出 \(q\) 所对应的贡献（预处理一个 \(S\) 给到的贡献系数）。

而第二部分的贡献由于 \(r\le \operatorname{mul}(S)\)，可以预存下系数最后直接算。一个 \(r\) 的贡献系数可以在询问前预处理出来。

复杂度就变成了 \(O(\operatorname{mul}(U)\times |U|+T\log^2 V\times Stuta)\)。

可以看到 \(|U|\) 取小一点且取小一点的质数会有用一些。

取 \(U=\{31,37,41,43\}\) 比较快。可能需要手写 hash_table 卡常。

CQBZ Round 34

T1

bot 有一个 \(n\) 个点的环，环上每个点有一个编号 \(a_i\)，保证 \(a_i\) 为 \(1 \sim n\) 的排列。

bot 要对排列中的一些元素染色，起初所有元素都是白色，bot 可以执行以下操作若干次：

将环上所有点分割成若干段，将每段中编号最大的点染黑。一个点可以被染黑多次。

bot 将染完色过后的颜色序列记为 \(s\)，其中 \(s_i = W\) 则代表编号为 \(i\) 的点最终为白色，\(s_i = B\) 代表最终为黑色。

不幸的是，bot 忘记他是如何染色的了，他只记得最终的序列 \(s\)。他现在想知道，想要得到 \(s\) 最少需要多少次操作，或者告诉他无论如何也得不到 \(s\)。

可以写一个笛卡尔树上 DP，发现令最大值处于首位算出来的最优。

T2

bot 有一个圈，圈上有 \(n\) 个点（保证 \(n\) 为偶数），每个点可以是黑色 \(b\) 也可以是白色 \(w\)。

我们称一个着色方案合法当且仅当黑色点和白色点的数量都是偶数。

对于一个合法的着色方案 \(c\)，定义其价值 \(f(c)\)：

把圈上所有点两两配对，只允许同色的点相互匹配。

对于每组配对的点两两连边，边的颜色为与两端点的颜色相同，这会形成 \(\frac{n}{2}\) 条边。

记 \(w\) 为当前连边方案中，异色且相交的边的对数。

\(f(c)\) 即为所有连边方案中，\(w\) 的最小值。

现在 bot 给你一个长度为 \(n\) 由 \(b, w, ?\) 组成的字符串 \(s\)，表示一个点的颜色或未确定。你需要对所有能形成的合法着色方案，计算其价值和对 998244353 取模的值。

此外，bot 会给你 \(m\) 次修改：

\(l \ r \ x \ y \ z\)，表示同时把 \(s_l \sim s_r\) 中的所有 \(w\) 替换为 \(x\)，\(b\) 替换为 \(y\)，\(?\) 替换为 \(z\)。

你需要在初始时和每轮修改后帮 bot 求出答案。

关键是发现 \(f\) 的计算方法。

考虑经典操作：用一个栈从左往右扫，能匹配就匹配，匹配不了就塞栈里。

由于只有双色，显然这个对数就是最终栈的大小除以四，即 wbwbwbwb 这种形式。

怎么算呢？答案是 \(\frac{|w_{even}-w_{odd}|}{2}=\frac{|b_{even}-b_{odd}|}{2}\)。

那么如何快速算一个固定局面的答案？

我们只在乎固定奇偶位置的 \(w\) 和问号，不妨设为 \(we,wo,qe,qo\)，答案就是：

\[\begin{aligned} &\frac{1}{2}\sum_{i=0}^{qe}\sum _{j=0}^{qo}{qe\choose i}{qo\choose j}|we+i-wo-j|[i+j+we+wo\equiv 0\bmod 2]\\ =&\frac{1}{2}\sum_{K=-qo}^{qe}|we-wo+K|\sum{qe\choose i}{qo\choose i-K}[K+we-wo\equiv 0\bmod 2]\\ =&\frac{1}{2}\sum_{K=-qo}^{qe}|we-wo+K|\sum{qe\choose i}{qo\choose qo-i+K}[K+we-wo\equiv 0\bmod 2]\\ =&\frac{1}{2}\sum_{K=-qo}^{qe}|we-wo+K|{qe+qo\choose qo+K}[K+we-wo\equiv 0\bmod 2]\\ =&\frac{1}{2}\sum_{K=0}^{qe+qo}|we-wo+K-qo|{qe+qo\choose K}[K+we-wo\equiv 0\bmod 2]\\ =&\frac{1}{2}\sum_{K=0}^{qe+qo}|we-wo+K-qo|{qe+qo\choose K}[K+we-wo\equiv 0\bmod 2]\\ \end{aligned} \]

整理一下，我们要算这样的式子：

\[\begin{aligned} S(X,Y,v=0/1)&=\sum_{i=0}^{2i+v\le Y}|X+2i+v|{Y\choose 2i+v}\\ &=\sum_{2i+v\ge -X}^{2i+v\le Y}(X+2i+v){Y\choose 2i+v}\\&+\sum_{2i+v< -X}^{2i+v\le Y}(-X-2i-v){Y\choose 2i+v} \end{aligned} \]

拆分并借助差分（对下界的差分，将下界统一为 \(0\)），以及正负性的转化后（转为正数），可以得到要计算：

\[T(X,Y,Z,v)=\sum^{2i+v\le X}{Y\choose 2i+v}(Z+2i+v) \]

借助 \({n\choose m}={n-1\choose m}+{n-1\choose m-1}\)，得到：

\[\begin{aligned} T(X,Y,Z,v)&=\sum^{2i+v\le X}{Y\choose 2i+v}(Z+2i+v)\\ &=\sum_{i=0}^{X-1}{Y-1\choose i}(Z+i+g(i)) \end{aligned} \]

其中 \(g(i)\) 是一个奇偶性有关的函数。

拆开 \(g\)（是一个只对奇/偶的组合数定上标前缀和）。

然后拆开 \(Z\)，并用吸收恒等式吸收 \(i\)，最后都可以转化为求组合数定上标前缀和。

使用莫队计算即可。

T3

在游戏《旧日争霸》中，有 \(n\) 个关卡，通过第 \(i\) 个关卡可以获得 \(v_i\) 枚金币，同时，挑战每个关卡时不能拥有过多金币，在关卡 \(i\) 时，你最多只能拥有 \(d_i\) 枚金币。具体来讲，如果你有 \(x\) 枚金币，通过关卡 \(i\) 后金币会变为 \(\min(x + v_i, d_i)\)。

bot 有 \(m\) 次询问，每次给出 \(l, r, x\)，表示你初始有 \(x\) 枚金币，你需要选择 \([l, r]\) 中的一个子段 \([l', r']\)，使得依次通过 \(l' \sim r'\) 的所有关卡后拥有的金币最多，注意你可以不选任何子段。

形式化地说，定义 \(f(l, r, x)\) 为：你初始时有 \(x\) 枚金币，依次通过从 \(l\) 到 \(r\) 的关卡后拥有的金币数。你需要求出：

\[\max \left\{ \max_{l \leq l' \leq r' \leq r} f(l', r', x), \ x \right\}. \]

给好几个做法。

sol1

注意到分段函数可以合并，可以考虑分块，块内 \(\sqrt n\times \sqrt n\) 个，还有最优前缀函数集合，最优后缀函数集合。

利用基排线性筛掉不可能最优的函数。

查询时，逐整块查询，需要支持找到最优的函数，可以基排后双指针。

sol2

线段树维护分段函数。

注意到左区间的最优后缀集合和右区间的最优前缀集合可以双指针合并，间接说明分割点只会产生线性个最优函数。

由此可以线段树直接处理出每个节点的最优前后缀和整体函数。

再去 \(\log ^2\) 单次查询。

sol3

std 做法。

大概就是考虑每个位置从它的上界出发再一直走重新顶到上界的位置设为 \(to\)。

然后按 \(x\) 排序后离线维护每个 \(to\) 的变化，可以证明变化量线性，用 LCT 维护支持加边断边链 max。

CQBZ Round 33

link

比较便秘。

T1

T1 看出结论是容易的，即胜负是最大值赢第一轮， \(4n-t+1\sim 4n\) 全部按递增顺序出现，且都是交替属于两队，且 \(4n-t\) 打破了这个交替或者顺序，它属于哪队就是哪队赢第二轮。

计数的话，考虑将胜负化为 \(0/1\) 的情况，枚举 \(4n\)，此刻每个 \(0/1\) 变化点就是胜负交替点，即这个循环移位变动的是 \(4n\)。

大力分讨一堆就可以了。

T2

神秘做法：
随机一个排列 \(p\) 代表最后每个位置的颜色。

每次每个人扔的时候，如果它有不需要的，就把不需要颜色的，距离这个颜色的匹配位置最远的颜色扔出去，否则全相同，只能随便扔一个。

正确率非常高。

正经做法：

考虑 \(n\times m\) 的矩阵，每个元素出现 \(m\) 次（有 \(m\) 整数倍就拆为多个元素，如果次数不能被 \(m\) 整除无解）。

行列连边，是一个 \(|L|=|R|=n\) 的二分图，跑 \(m\) 正则匹配。

然后将每一行重新排列，使得每一列都是一个排列。

现在就是我们想要让每一列都变成一个同样的排列。不妨考虑将其都变为第一列的排列，重标号一下就是全部变成 \(1\sim n\)。

怎么操作呢？

考虑现在你可以行间任意交换代价 \(0\)，列循环移位 \(k\) 是代价 \(k\)。

一列一列考虑，找同一个置换环上的位置 \(p_i=x,p_j=y\)，引入一个辅助列：

做如下操作：

\[\begin{bmatrix} x&a\\ y&b \end{bmatrix} \implies \begin{bmatrix} a&x\\ y&b \end{bmatrix} \implies \begin{bmatrix} a&?\\ y&x\\ ?&b \end{bmatrix} \implies \begin{bmatrix} a&?\\ x&y\\ ?&b \end{bmatrix} \implies \begin{bmatrix} a&y\\ x&b \end{bmatrix} \implies \begin{bmatrix} y&a\\ x&b \end{bmatrix} \]

一次可以拆掉一个环，但代价到 \(n\) 了。

考虑并行，对于每个置换环，相邻点两两配对为 \((x,y)\)，最后剩下一个（可能）先不管。

随便拿一个辅助列过来，我们不关心 \(a,b\) 具体值。

做一个完整的 \(n\) 的轮换即可完成所有交换。

现在只剩下若干二元环了，再做一次即可。

这样是 \(2n(m-1)\) 的。

单次 \(2n\) 比较差，注意这个操作不会改变辅助列，这启发我们找一个单次 \(n\) 的但不保证不改变辅助列的方法过来。

其实可以将辅助列一直转，因为辅助列是一个排列，所以转的过程中，可以将每个位置的值直接放到真实列里去（和真实列作交换）。可以保证一轮后真实列就是 \([1,\dots ,n]\)。

即：转的过程中，若辅助列的值 \(i\) 转到了第 \(i\) 行且没交换过，直接和真实列作交换。

最后只剩下最后一列有点问题，作我们这个 \(2n\) 单次的构造即可。

\(n(m-2)+2n=nm\)