ECFINAL2025游记 & 部分题解

· · 生活·游记

前言

我发现我写的东西只能投游记分类才有可能被国内看到喵。所以主播决定在前面先写一篇游记镇楼。

闲话

1.31 以前

HdU 寒假时间肥肠晚，我们是 21 号考完试，也就是说相比其他放假早的学校，我们少了约半个月的训练时间。

然后嘎巴嘎巴 22 号开始训练，每天准时早上 9:00 到下午两点 2:00 一场模拟赛。

不过在这里我要陈述我的罪孽：

所以，主播的实力并没有提高多少。。。

不过，主播目前正在实施以下改革：

希望这学期能变得更强一点啊吧啊吧。

1.31

出发白金汉爵大酒店。不过我怎么没有遇到一场比赛是在 zJu 里面办的，想起逛逛 Zju 的校园 qaq。

酒店大大的，配有自助食堂（与其他酒店不同，这里是三餐都有提供，并且有各种各样的吃食），地下房间（第一次看见酒店在地下还设有房间），很多会议厅。其他地方到没有逛过。

果然，ll 因为地下房间便宜特地给我们定了地下房间，好像 300 左右一晚。房间虽然没有窗户但有窗帘（？），还有一个很哇塞的浴缸。

浴缸耶！我要泡澡！

吃完晚饭后到大厅逛了逛，看到了 Qingyu 和 Jiangly 一行人（我只认识两个）。太过社恐，只能一边假装有事情乱走一边偷偷看他们在干嘛 qaq，但也没有看出一个所以然来。。。

然后回去泡澡，泡澡好舒服啊 ~ 。可能泡太久了，泡完顿时感觉身体变虚了，还流了好多鼻血 \~。

早早睡觉。结果 0 点半被舍友的键盘声、鼠标声和忽巨亮忽暗的屏幕吵醒。当时一方面觉得本次比赛大概率打成 SB，一方面想直接喷脏话。。。气笑了，以后一定要自己破费一间房，信舍友不影响我睡觉不如信我是秦始皇。。。

2.1

早上醒来果然头巨 TM 痛。今天彻底放弃干任何事，希望好好休息。然后被队友拉去打华为挑战赛。基本坐着盯着队友写了三个小时，虽然一分木有。

晚上受不了了，直接打车逃回 hDU，早早睡了。

2.2

由于赶过去还有一个小时，所以 7 点早起赶车，果不其然，头还是一直在痛，除非队友发挥超常，不然也就这样了。

比赛开始。

开头看了 B， 由于头巨痛，给队友说了下题意和思路，让队友写了。

然后在想 K。期间队友过来问 J 有什么思路。大脑短路 5 分钟后给了个提示队友就会了。

然后继续想 K，想了一万年终于会了跟队友说了思路让队友上去写过了。

然后看 H，想了一会发现是个简单题，但是大概率要考虑精度细节，就把思路跟队友说了让队友上去写。

然后两个队友调了近两个小时的 H。。。

当时去看 I，过了半小时差不多会了，但是由于头痛细节实在想不清，由于队友都没空只能努力自己上去写。期间和队友交流了一下思路，结果一个小错误直到结束都没有发现只能边头痛边盯着看。。。

然后最后一个小时队友在写 A，我不会几何就没有过去参和，不过事后补了感觉分类讨论也没有多少，样例也有给提示，感觉得想清楚再写题啊。

然后比赛就结束了。

嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤。

What can I say,man……我感觉我确实尽力了。。。。。。

队友觉得打的太差，一个滚回房间，一个跑去跟群友面基了，只留下我一个人痛苦的接受审判。

这几天到时没有看到 HZY，不过 HZY 已经要去 WorldFinal 了，嘤嘤嘤嘤嘤嘤嘤嘤嘤。

比赛完遇到了 O(4) 个高中同学，和他们瞎聊了会天。

唉，上次相见还是半年以前，那么快就物是人非了。。。。。。在这里祝他们前程似锦吧。。。

接着是领奖环节，在颁发中学生奖的时候现是 hzg 匆忙上台一边带领一边寻找 wmy，所幸最后 wmy 也是成功站上奖台领奖了！（此处应有图但我手机里的图消失了，所以各位自行脑补即可）

最后一直待到了最后，看到冠军上去领奖。往常我可能会说一句什么“大丈夫当如是也”，但那刻心里只有说不出口的茫然和失落。

这次比赛一队最终还是没有出线，遥想我当年还是初中生的时候，就听过教练吹嘘 hzk 多么强劲，当时只会阿巴阿爸仰望，结果这三年时光竹篮打水一场空。唉。

感觉离我近的都没啥好事，还能咋滴，继续努力吧。努力会欺骗你，但努力至少会让自己心安一点。

题解

:::info{open} 较为简单的四个题（B,H,J,K）主播没有写题解，不会写的自己回去面壁思过。

G 题待补，可以上 qoj 参考官方题解。

不会的问题可以问 AI。请不要质疑 AI 的实力，AI 肯定比你强。

:::

A

:::info[题面]

给定 \Delta ABC，直线 l_1 经过线段 AB，直线 l_2 经过点 C，且 l_1||l_2。

定义 "好密铺" 为用全等于 \Delta ABC 的三角形（允许旋转，翻转，平移）恰好密铺 l_1 和 l_2 间的区域。且每个三角形同时和两个直线相接触。

给定点 D，问是否存在一种"好密铺"，使得 D 恰好在一个三角形的边上。

:::

一个直觉猜想是三角形的三个点应该都在两条直线上，否则不大好做： :::info[证明]

假设 \Delta ABC 的顶点 C 不在两条直线上，那么考虑 \angle EAC 所在的三角形（假设为 \Delta EAD）

由于 \Delta EAD 的顶点 AE 在一条直线上，那么 D 一定在另一条直线上，即 \overrightarrow{AC}||\overrightarrow{AD}。

那么依照图示，在确定完 \Delta EAD 之后，\Delta BCD 也被确定了，而这个三角形不满足题示条件（没有触碰到上面的横线），所以矛盾。 ::: 那么即对于一个三角形，恰好有两个顶点在一条直线上。

接下来就应该讨论可能的摆放方案了：假设已经确定了 \Delta ABC，我们要来确定右侧三角形的方案（假设为 \Delta ACD）

  • 再考虑 C,D 在同一条直线的情况，显然需要 \angle ACB=\frac{\pi}{2}。没有其他限制。

那么，依据 D 所在位置的分类进行讨论，应当会不重不漏。我们只需要对于上面两种情况计算答案即可。

我们可以把上述密铺的构造看成线段 AB,BC,AC 朝着左右平移，每次平移 |BC| 个单位。

如果 D 不在 l_1 或 l_2 上且在 l_1,l_2 围成的带状区域内，那么 D 一定被 AB 或 AC 平移的线段经过。假设 D 被 AC 平移的线段经过，即:

\overrightarrow{OD}=\overrightarrow{OA}+\lambda\overrightarrow{AC}+k\overrightarrow{BC},k\in Z,\lambda \in[0,1]

上面的式子不大好算，我们可以转变视角：我们可以把 AC 往 D 所在的方向平移，若恰好平移整数个 \overrightarrow{BC} 能经过 D，则满足条件；否则不满足条件。

那么这样子就比较好算了。

设 l_3||AB 且 D\in l_3，我只需要保证 D 到 AB 的距离整除 C 到 AB 的距离即可，即 \frac{\overrightarrow{AB}\times \overrightarrow{BC}}{|AB|}|\frac{\overrightarrow{AD}\times \overrightarrow{AB}}{|AB|} 即可。

由于上面的讨论，我们以两个三角形构建成的一个矩形为单元来看，矩形的对角线可能有两种情况。需要额外注意如果题目中的点 D 在对角线 DB 的平移上，他显然不能在矩形 ABCD 内。

最后，D 的初始坐标可能是分数，不过坐标范围很小，可以先对所有点统一通分把分数去掉之后再做，需要 __int128 存储。 :::info[代码]

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long 
#define int long long 
using namespace std;
struct Point
{
    i128 x,y;Point(i128 x=0,i128 y=0):x(x),y(y){}
    friend const Point operator+(const Point&lhs,const Point&rhs){return Point(lhs.x+rhs.x,lhs.y+rhs.y);}
    friend const Point operator-(const Point&lhs,const Point&rhs){return Point(lhs.x-rhs.x,lhs.y-rhs.y);}
    const Point operator*(const i128&rhs){return Point(x*rhs,y*rhs);}
    void read(){int _x,_y;cin>>_x>>_y;x=_x,y=_y;}
};
i128 dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
i128 cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
i128 cross(Point A,Point B,Point C){return cross(B-A,C-A);}
Point A,B,C,D,V,P;
int check(Point X,Point Y,int k0)
{
    i128 v1=cross(Y-X,D-X);
    i128 v2=cross(Y-X,V);
    if(v1%v2==0&&(!k0||(k0&&v1)))return 1;
    return 0;
}
void solve()
{
    int xd1,xd2,yd1,yd2;    
    A.read();B.read();C.read();cin>>xd1;cin.get();cin>>xd2>>yd1;cin.get();cin>>yd2;
    i128 l=(i128)xd2*yd2/__gcd(xd2,yd2);
    A=A*l,B=B*l,C=C*l,D.x=(i128)xd1*l/xd2,D.y=(i128)yd1*l/yd2;
    V=B-A;
    if(cross(V,D-A)==0){cout<<"Yes"<<endl;return;}
    if(cross(V,D-C)==0){cout<<"Yes"<<endl;return;}
    if((cross(V,D-A)>0)==(cross(V,D-C)>0)){cout<<<"No"<<endl;return;}
    if(check(A,C,0)||check(B,C,0)){cout<<"Yes"<<endl;return;}
    if(dot(C-A,B-A)==0&&check(A,C+B-A,1)){cout<<"Yes"<<endl;return;}
    if(dot(C-B,A-B)==0&&check(B,C+A-B,1)){cout<<"Yes"<<endl;return;}
    cout<<"No"<<endl;
}
signed main()
{
    int _;cin>>_;while(_--)solve();
}

:::

C

:::info[题面] 给定长度为 n 的序列 a_1,a_2...a_n。对于 k\in[1,n]，分别求出下面式子的值：

\sum_{i=1}^{k}\max_{v\ge a_i}(-(v-a[i])+\sum_{j=i+1}^{k}[a_i<a_j\le v])

其中 n\le 10^5 ::: 观察一下式子的结构， 虽然式子里限制的 [a_i<a_j\le v] 容易拆成 [a_j\le v] 加上一些容易计算的式子，但是 \max_{v\ge a_i} 的限制仍然无法摆脱。

因此，我们转换思路，考虑一个构造，将 v\in[a_i,n] 按照线段树的方式划分成 \log 个区间。这个构造有一个显著的优点：对于某个值 a_j，他最多只涉及到 O(\log n) 个区间需要复杂的计算。

略微观察，对于某一个 i 来说，随着 k 的增大，最优 v 的取值肯定是单调不降的： :::info[证明] 我们维护数组 b，b[i] 表示 i=v 的时候的答案。显然，当 k 增加的时候，增加的值为：\forall v\ge a_{k+1} \And a_{k+1}>a_i,b[v]\to b[v]+1，即 b 数组中的一个后缀的值增加 1。

那么假设 b[v']>b[v],v'>v。那么当 b[v] 增加时，由于 b 数组的一个后缀会增加，因此 b[v'] 也会增加，即有 \Delta b[v']\ge \Delta b[v]，可以始终推出 b[v']>b[v]。即 v 的最优取值单调不降 :::

那么我们按照上述将 [a_i,n] 划分成 \log 个区间。那么，我们要完成三件事：

Q1

我们考虑线段树上的一个区间 [l,r] 和一个下标 i。我们转化一下下标 i 对 k 贡献的式子：

\max_{v\in [l,r]}(\sum_{j=i+1}^{k}[v< a_j\le v]-(v-l))\\ +\sum_{j=i+1}^{k}[a_i<a_j\le l]+(l-a[i]) 图论巨佬可以看出这个式子接近一个扩展 Hall 定理的形式： > **扩展 Hall 定理** > >对于二分图 $G=(V,E)$，设 $L$ 为其左部点构成的集合，$R$ 为其右部点构成的集合。那么二分图的最大匹配为： >$$ >|L|-\max_{S\in L}(|S|-|N(S)|) >$$ >其中 $N(S)$ 表示右部点 $R$ 中所有与集合 $S$ 内的点有边相邻的点构成的集合。 我们把 $|S|$ 看成 $\sum_{j=i+1}^{k}[a_j\le v]$，$N(s)$ 看成 $(v-l)$，构造对应的二分图。 > 构造左部点为 $l<a_j,j\in[i+1,k]$，右部点为 $v,v\in[l,r]$。其中点 $a_j$ 向 $[l,a_j]$ 连边。 > >可以看出 $|N(S)|$ 肯定是右部点的一个前缀，那么我们想让 $|S|$ 尽可能大，那么肯定取满足 $a_j\le v$ 的所有点，这样 Hall 定理中的 $\max$ 形式就和我们要求的 $\max$ 式子一样了。 那么，我们对于一个下标 $i$ 和区间 $[l,r]$，我们维护这个区间的二分图的最大匹配的左部点。当 $k$ 增加时，若最大匹配没有增加，则答案增加。 :::::info[如何维护不同 $i$ 的二分图] 但我们发现对于每个不同的 $i$，左部点构成的集合可能不同，不过这个形式很像是线性基，具体来说把 $a_j$ 看成一个二进制的值为 $a_j-l$ 个 $1$ 构成的元素，那么最大匹配就相当于这个线性基里的元素个数。 如果做过 CF1100F，可以知道线性基有一个特殊方法叫做"前缀线性基"： > 对于一个序列 $a_1...a_n$，我们按如下插入 $a_i$，并把被替换的下标最小的元素踢出线性基，记此刻的线性基为 $L_i$。 > 那么，对于 $[l,r]$ 构成的一个线性基，就是 $L_r$ 里保留下标 $\ge l$ 的元素所构成的线性基。 :::info[证明] 那么，我们把 $a_x$ 按照剔除最小下标的规则插入进 $L_r$ 里，因为 $a_x$ 不能替换 $L_r$ 的元素（已经 $a_x$ 之前被替换过了,且线性基中每个基的下标都是不降的），这证明 $L_r$ 里下标大于 $x$ 的元素可以组合出 $a_x$。而 $a_x$ 又在 $P$ 里，这证明大于 $x$ 的元素不能组合出 $a_x$，矛盾。那么 $x\in L_r$， 与此同时，若 $L_r$ 保留 $\ge l$ 的元素的大小还是一个线性基，因此元素个数小于等于 $|P|$。综上，这我们构造出来的线性基就等于 $P$。证毕。 对于区间 $[l,r]$，我们从 $r\to l$ 按照普通的线性基插入过程（插入后这个位置的元素不再改变）构造出一个线性基，记为 $P$。假设元素 $x\in P,x\not \in L_r$。 ::: 这告诉我们，对于区间 $[l,r]$，我们只需要维护最大匹配的左部点集合，设集合为 $V$，并在时及时踢出下标最小的元素。那么下标 $i$ 的最大匹配就是 $x\in V,x>i$。 换句话说，我们对于区间 $[l,r]$，维护集合 $V$，当 $k$ 增加时，若集合 $V$ 中的一个元素 $x$ 被踢出，那么 $i\le x$ 的下标的值会增加 $1$. ::::: :::info[如何维护集合 $V$] * 我们记 $b_{v-l}=(v-l)-\sum_{x\in V}[l<x\le v]$，即用 $V$ 中值小于等于 $v$ 的节点去匹配（不考虑边的限制） 下标在 $1$ 到 $v-l$ 中剩下的右部点个数。 * 当左部点新增加一个数之后，若存在 $b_i<0$ 的位置，这证明 $V$ 中需要剔除一个点；否则 $V$ 中的元素一定都有合法匹配，即最大匹配数加一。我们找到 $b_i<0$ 的一个最小的 $i$。为了满足 $\forall i,b_i\ge 0$，我们需要剔除一个值在 $1$ 到 $i$ 的一个且在 $V$ 内的元素。 用线段树维护上述操作即可。 ::: 经过上述讨论，现在对于每个区间 $[l,r]$，我们能用 $O(\log n \sum_j a_j\in[l,r])$ 的时间求出若干条二元组 $(k',i')$，我们把区间 $[l,r]$ 构成的集合称作 $V_{l,r}$： * 当 $k\ge k',i\le i'$ 时 $\max_{v\in [l,r]}(\sum_{j=i+1}^{k}[v< a_j\le v]-(v-l))$ 的贡献增加 $1$。 那么这部分的时间是 $O(n\log^2n)

最后我们可以换一下 \max 贡献的式子：

\sum_{(i',k')\in V_{l,r}}[k'\le k\And i\le i']

Q2

经过 Q1 的讨论，我们能够快速计算出给定任意一个 (i,k)，在某个区间 [l,r] 获得的贡献：

\sum_{(i',k')\in V_{l,r}}[k'\le k\And i\le i'] +\sum_{j=i+1}^{k}[a_i<a_j\le l]+(l-a[i])

对于 \max 的贡献，我们对区间 [l,r] 建出主席树，第 i 棵树维护下标为 i 的答案，对于线段树上的一个节点 x，对应区间为 [a,b]，贡献为 \sum_{(i',k'),i'\le i,k'\in[a,b]}1 ，其中 (i',k') 是 Q1 中的修改序列。（离散化一下）

对于后面 \sum 的贡献，我们建立全局主席树，第 i 棵树维护值为 i 的时候，下标取 [l,r] 时候的 \sum_{j\in[l,r]}[a_j\le i] 的值。

那么我们考虑下标 i 切割出的所有区间：[l_1=a_i,r_1],[l_2=r_1+1,r_2]...[l_{m}=r_{m-1}+1,r_m=n]。并希望求出 [lk_j,rk_j]，满足当 v\in [l_j,r_j] 时，只有满足 k\in[lk_j,rk_j] 时贡献最大。

由于 k 的取值有决策单调性，那么我们套用决策单调性单调栈优化的求法，再套用主席树二分（因为在比较两个区间中需要的主席树的树根并没有变动）求出 k 的临界取值即可。

可以看出，共 O(n\log n) 个区间，操作复杂度为 O(\log n)，复杂度为 O(n\log^2 n) :::warning 主席树二分中注意要保证 k\ge i，并且不能计算 k<i 的贡献。可以在开始时候减去 [1,k-1] 的贡献，并跳过下标属于 [1,k-1] 的比较 :::

Q3

接下来就要开始计算答案了，我们再看一下答案式子：

\sum_{i=1}^{k}(\sum_{(i',k')\in V_{lk_i,rk_i}}[k'\le k\And i\le i'] +\sum_{j=i+1}^{k}[a_i<a_j\le lk_i]+(lk_i-a[i]))

考虑对 k 进行扫描线。维护 k 增加时答案的变动。

对区间 [l,r] 开两个大小为 |V_{l,r}| 的树状数组，分别维护 v 落在当前区间的所有下标 i（可以按 i' 进行离散化），和维护 \forall (i',k'),k'\le k 的 i'。

这样，当 k 增加时，可以查询能贡献到的下标 i；当 i 所属区间变化时，我们可以查询 i' 知道 i 在这片区间时候的总贡献。方便进行增加去除。

后面 -a_i 可以直接累加；lk_i 可以在 i 所属的区间变动时更新贡献。前面的贡献可以拆成：

\sum_{j=i+1}^{k}[a_j\le lk_i]-\sum_{j=i+1}^{k}[a_j\le a_i]

同理，我们开两个树状数组维护 lk_i 和 a_i。在 k 增加时可以快速获得新增的贡献；在 lk_i 变动时可以使用 Q2 中的主席树快速计算出式子的值。

综上，整道题可以在 O(nlog^2 n) 的时间复杂度内解决。

代码写的很抽象，谨慎观看：

:::info[代码]

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define ll long long 
#define mid ((L+R)>>1)
using namespace std;
const int N=1e5+100,M=N*300,inf=1e9+7;
int n;
int A[N];
ll ans[N];
vector<tuple<int,int,int>>aseg[N];
//aseg[i] 维护点 i 的修改区间 (x,l,r)，表示线段树上的节点和对应区间
vector<int>g[N];
vector<pii>nopt[N<<2],q[N][2];
//nopt[k'] 维护 (x,i') 修改，x 是线段树节点
//q[k][0] 加入，q[k][1] 删除，维护 (x,i)
int ch[N];
BIT ca,cv;

namespace data_structure
{
    struct Node//主席树节点
    {
        int val,ls,rs;Node(int val=0,int ls=0,int rs=0):val(val),ls(ls),rs(rs){}
    }a[M];
    int st[M],top,cnt;
    int New(){return top?st[top--]:++cnt;}
    void del(int&x){a[x]=Node();st[++top]=x;x=0;}
    struct Persistent_Tree//所需要的主席树可以都改成单点修改，区间查询
    {
        void update(int&x,int y,int L,int R,int p,int v)
        {
            x=New();a[x]=a[y];
            if(L==R){a[x].val+=v;return;}
            if(p<=mid)update(a[x].ls,a[y].ls,L,mid,p,v);
            else update(a[x].rs,a[y].rs,mid+1,R,p,v);
            a[x].val=a[a[x].ls].val+a[a[x].rs].val;
        }
        int query(int x,int L,int R,int l,int r)
        {
            if(!x||l>r)return 0;
            if(l<=L&&R<=r)return a[x].val;
            int res=0;
            if(l<=mid)res+=query(a[x].ls,L,mid,l,r);
            if(r>mid)res+=query(a[x].rs,mid+1,R,l,r);
            return res;
        }
    }PT;
    struct PT1//主席树，以值为版本，rt[i] (l,r) 维护 l<=pos<=r,a[pos]<=i 的个数  
    {
        int rt[N];
        int query(int x,int y,int l,int r){return PT.query(rt[y],1,n,l,r)-PT.query(rt[x-1],1,n,l,r);}
    }PT1;
    struct Set_Tree//线段树维护二分图左部点集合
    {
        #define ls (x<<1)
        #define rs (x<<1|1)
        int val[N<<2],mn[N<<2],laz[N<<2];
        //val[x] 表示 区间长度减去区间内点的数量，mn[x] 表示区间内集合点的最小编号，laz[x] 表示懒标记，vis[x]表示是否修改过
        bitset<N<<2>vis;
        queue<int>vt[N];//每个叶子节点的集合点编号可能不止一个，因此用队列维护
        Set_Tree(){vis.reset();vis=~vis;}
        void push(int x,int v){val[x]+=v,laz[x]+=v;vis[x]=1;}
        void pushdown(int x){if(!laz[x])return;push(ls,laz[x]);push(rs,laz[x]);laz[x]=0;}
        void pushup(int x){val[x]=min(val[ls],val[rs]);mn[x]=min(mn[ls],mn[rs]);}
        void build(int x,int L,int R)//因为每个叶子节点的初值不好直接维护，因此改成重置被修改过节点的值
        {
            laz[x]=vis[x]=0;
            if(L==R){val[x]=L,mn[x]=inf;while(!vt[L].empty())vt[L].pop();return;}
            if(vis[ls])build(ls,L,mid);if(vis[rs])build(rs,mid+1,R);
            pushup(x);
        }
        pii querypos(int x,int L,int R,int tag=0)//查询区间内val<0的最小位置，如果没有返回inf，如果tag=1则查询区间内mn最小的位置
        {
            vis[x]=1;
            if(L==R){return mk(L,mn[x]);}
            pushdown(x);
            if(val[ls]<0)return querypos(ls,L,mid,tag);
            if(val[rs]>=0)
            {
                if(!tag)return mk(inf,inf);
                return mn[ls]<mn[rs]?querypos(ls,L,mid,tag):querypos(rs,mid+1,R,tag);
            }
            pii res=querypos(rs,mid+1,R,tag);
            if(res.se>mn[ls])return querypos(ls,L,mid,tag|1);
            return res;
        }
        int del(int x,int L,int R,int p)
        {
            vis[x]=1;
            if(L==R)
            {
                int v=mn[x];
                if(!vt[L].empty())mn[x]=vt[L].front(),vt[L].pop();else mn[x]=inf;
                return v;
            }
            pushdown(x);
            int res;
            if(p<=mid)res=del(ls,L,mid,p);else res=del(rs,mid+1,R,p);
            pushup(x);
            return res;
        }
        void update(int x,int L,int R,int l,int r,int v)//区间修改
        {
            vis[x]=1;
            if(l<=L&&R<=r)return push(x,v);
            pushdown(x);
            if(l<=mid)update(ls,L,mid,l,r,v);if(r>mid)update(rs,mid+1,R,l,r,v);
            pushup(x);

        }
        void add(int x,int L,int R,int p,int v)//新加入一个集合内的点
        {
            vis[x]=1;
            if(L==R){if(mn[x]==inf)mn[x]=v;else vt[L].push(v);return;}
            pushdown(x);
            if(p<=mid)add(ls,L,mid,p,v);else add(rs,mid+1,R,p,v);
            pushup(x);
        }
        #undef ls
        #undef rs
        void build(){build(1,1,n);}
        int querypos(){return querypos(1,1,n).fi;}
        int del(int p){return del(1,1,n,p);}
        void update(int l,int r,int v){update(1,1,n,l,r,v);}
        void add(int p,int v){add(1,1,n,p,v);}
    }ST; 
    struct BIT
    {
        #define lb(x) ((x)&(-(x)))
        int sz;vector<int>vt;
        void resize(int _sz){sz=_sz+1;vt.resize(sz);}
        void clear(){vt.clear();}
        void add(int x,int y){for(;x<sz;x+=lb(x))vt[x]+=y;}
        int ask(int x){if(x<0)return 0;int t=0;for(;x;x-=lb(x))t+=vt[x];return t;}
        int ask(int l,int r){return ask(r)-ask(l-1);}
    };
    struct MainTree//线段树维护被划分区间
    {
        #define ls (x<<1)
        #define rs (x<<1|1)
        vector<pii>rt[N<<2],opt[N<<2];
        //rt 维护当前区间的 (i,\forall i<= i'(i',k')修改对应的主席树)，并按 i 升序排序
        BIT bt[N<<2][2];
        int tl[N<<2],tr[N<<2];
        //tl,tr 记录点 x 的区间左端点和右端点
        //opt[x] 维护当前区间的 (v,p) 修改，表示时刻 p 有一个值为 v 的点被插入了。
        int find(int x,int i){return (lower_bound(rt[x].begin(),rt[x].end(),mk(i,0)))->se;}
        //对于下标 i，我要所有 i<=i' 的操作构成的主席树，那么即找到>=i 的第一个节点
        int gpos(int x,int i){return (lower_bound(rt[x].begin(),rt[x].end(),mk(i,0))-rt[x].begin())+1;}
        void build(int x,int L,int R)
        {
            tl[x]=L,tr[x]=R;
            if(L==R)return;
            build(ls,L,mid);build(rs,mid+1,R);
        }
        void getseg(int x,int L,int R,int v,int p)
        {
            if(L==R)return aseg[p].push_back({x,L,R}),void();
            if(v<=mid)getseg(ls,L,mid,v,p),aseg[p].push_back({rs,mid+1,R});
            else getseg(rs,mid+1,R,v,p);
        }
        void ins(int x,int L,int R,int v,int k)
        {
            if(v<=R&&v>L)opt[x].push_back({v,k});
            if(L==R)return;
            if(v-1<=mid)return ins(ls,L,mid,v,k);else ins(rs,mid+1,R,v,k);
        }
        void add(int x,int L,int R)
        {
            ST.build(1,1,n);
            for(auto [v,k]:opt[x])
            {
                //a[time],time
                ST.update(v-L,n,-1);//注意右边界改为 n 没有问题，因为操作范围不会超过 r，所以不会有 r+1~n 出现值<0而 l~r 的值全部大于等于 0 的情况。即 r+1~n 不会影响答案
                ST.add(v-L,k);
                int p=ST.val[1]<0?ST.querypos():inf;
                if(p==inf)continue;
                int i=ST.del(p);
                ST.update(p,n,1);
                g[i].push_back(k);
                nopt[k].push_back({x,i});
            }
            bt[x][0].resize(opt[x].size()+3);bt[x][1].resize(opt[x].size()+3);
            rt[x].push_back({n+1,0});
            reverse(opt[x].begin(),opt[x].end());
            //因为 (i',k') 按 i' 是要从大往小加，所以要倒序
            for(auto [v,k]:opt[x])
            {
                rt[x].push_back({k,rt[x].back().se});
                for(auto pos:g[k])PT.update(rt[x].back().se,rt[x].back().se,1,n,pos,1);
                g[k].clear();
            }
            reverse(rt[x].begin(),rt[x].end());
            if(L==R)return;
            add(ls,L,mid);add(rs,mid+1,R);
        }
        #undef rs
        #undef ls
    }MT;
}
using namespace data_structure;

int search(int x,int y,int px,int py,int L,int R,int p,int vx,int vy)
/*
x,y 线段树区间内的主席树
px,py PT1 中的主席树
L,R 当前线段树区间
p 限制 k\ge p
vx,vy 当前的值
*/
{
    auto check=[&](int x,int y,int px,int py)
    {
        return vx+a[x].val+a[px].val>=vy+a[y].val+a[py].val;
    };
    if(L==R)return check(x,y,px,py)?L:0;
    if(mid<p||check(a[x].ls,a[y].ls,a[px].ls,a[py].ls))
        return max(mid,search(a[x].rs,a[y].rs,a[px].rs,a[py].rs,mid+1,R,p,
                              vx+a[a[x].ls].val+a[a[px].ls].val,
                              vy+a[a[y].ls].val+a[a[py].ls].val));
    return search(a[x].ls,a[y].ls,a[px].ls,a[py].ls,L,mid,p,vx,vy);
}
int cmp(int i,tuple<int,int,int>a,tuple<int,int,int>b)
{
    auto&[x,l,r]=a;auto&[nx,nl,nr]=b;
    int mx=MT.find(x,i),my=MT.find(nx,i);
    return search(mx,my,PT1.rt[l],PT1.rt[nl],1,n,i,
                    A[i]-l-PT.query(mx,1,n,1,i)-PT.query(PT1.rt[l],1,n,1,i),
                    A[i]-nl-PT.query(my,1,n,1,i)-PT.query(PT1.rt[nl],1,n,1,i)
                  );
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    MT.build(1,1,n);
    for(int i=1;i<=n;i++)cin>>A[i],MT.getseg(1,1,n,A[i],i),MT.ins(1,1,n,A[i],i);
    for(int i=1;i<=n;i++)g[A[i]].push_back(i);
    for(int i=1;i<=n;i++)
    {
        PT1.rt[i]=PT1.rt[i-1];
        for(auto x:g[i])PT.update(PT1.rt[i],PT1.rt[i],1,n,x,1);
        g[i].clear();
    }
    MT.add(1,1,n);
    for(int i=1;i<=n;i++)
    {
        struct sta//栈
        {
            tuple<int,int,int>v;
            int l,r;
            sta(tuple<int,int,int>v,int l,int r):v(v),l(l),r(r){}
        };
        stack<sta>s;
        for(int j=0;j<aseg[i].size();j++)
        {
            int l=i;
            while(!s.empty()&&(l=cmp(i,s.top().v,aseg[i][j])+1)<=s.top().l)s.pop();
            if(!s.empty())s.top().r=l-1;
            s.push(sta(aseg[i][j],l,n));
        }
        while(!s.empty())
        {
            int x=get<0>(s.top().v);
            int kl=s.top().l,kr=s.top().r;s.pop();
            if(kl<=kr)q[kl][0].push_back({x,i}),q[kr+1][1].push_back({x,i});
        }
    }
    ll res=0;
    ca.resize(n+2);cv.resize(n+2);
    for(int k=1;k<=n;k++)
    {
        for(auto [x,r]:nopt[k])
        {
            res+=MT.bt[x][0].ask(1,MT.gpos(x,r));
            MT.bt[x][1].add(MT.gpos(x,r),1);
        }
        for(int opt=1,v=-1;opt>=0;opt--,v*=-1)
            for(auto [x,i]:q[k][opt])
            {
                res-=MT.tl[x]*v;
                res+=MT.bt[x][1].ask(MT.gpos(x,i),MT.bt[x][1].vt.size()-1)*v;
                MT.bt[x][0].add(MT.gpos(x,i),v);
                res+=PT1.query(A[i]+1,MT.tl[x],i+1,k-1)*v;
                cv.add(MT.tl[x],v);
            }
        res+=A[k];
        ca.add(A[k],1);
        res-=ca.ask(A[k],n);
        res+=cv.ask(A[k],n);
        ans[k]+=res;
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
    return 0;
}

:::

D

:::info[题面] 给定一个长度为 n 且只包含 01 和 ? 的字符串。

两人博弈，先手的每回合会将一个 ? 变为 0，后手的每回合会将一个 ? 变为 1，当没有问号时游戏结束。

定义游戏结束时的分数为：最长的只包含0的区间长度。先手想要最大化分数，后手想要最小化。若双方均采取最优策略，求最终的分数。

n\le 10^5,\sum n\le 10^6

:::

显然，因为最终串的 0 的区间不可能跨过原串中 1 的位置，我们应该可以将串按 1 分割成多个子问题来考虑。

:::info[略微证一下] 假设 S_{l,r} 被分割成了一个子游戏且若双方只在这个子游戏内操作时的分数最大，记为 v。

显然，若先手在原串内按子游戏的方案操作，当后手不选择在这个子游戏内操作时，相当于先手凭空在这个子游戏内多出了一轮，这个子游戏内的分数不会变小；因此，后手也必须在这个子游戏内操作，那么最大分数至少是 v。

同时，若先手选择一个原串的子游戏先操作，后手可以跟着在上一轮先手操作的子游戏内操作，这样每个子游戏的贡献不会超过原本只在子游戏内操作的贡献，即最大值至多是 v。

综上，答案就是每个子游戏的分数的最大值。 :::

接下来我们讨论单个子游戏（记为 T。显然，T 里面只有 0 和 ?）的解法。

方法 1.

稍微模拟一下会发现，后手操作很像上文中提到的子游戏，但分割的两端之间的状态会有一些变化（可能一些问号已经被操作变成 0）。我们猜想能不能通过最优化排除掉一些不方便进行设计的状态。

进一步，我们发现，在第一轮中，假设先手操作了位置 x，后手操作了位置 y，且 x<y 的前提下，那么我们不需要考虑 y+1...n 构成的子游戏的贡献。（反之同理）

:::info[证明] 根据之前的结论，y 将 T 划分成了两个子游戏 A 和 B（A=T_{1,y-1} 且 A[x]='0'，B=T_{y+1,|T|}）。若 A 的分数更大，根据上文推导显然不用管 B。

那么若 B 的分数更大，我们考虑如下的一个构造：

对于 T，先手忽略 T_{1..y} 的位置来操作。先手第一步走 B 到达最优分数的构造的第一步。此后，若后手选择走在 T_{y+1...|T|} 内，照搬 B 游戏的策略；若后手走在 T_{1...y}，则先手随便。这样必然能构造出一个分数至少为 B 游戏到达的分数的方案。

感性理解就是 B\in T，那么我按 B 中的策略走答案至少是 B 游戏的分数。

既然我第一轮走 B 至少是这个分数。那么我在 x<y 的时候时就不需要考虑游戏 B 对答案的贡献。

:::

然后，我们在考虑 y 的性质，既然当选择 y 后，按照 y 和 x 的相对顺序，下一步的子游戏选择已经确定了，那么 y 肯定要让这个子游戏尽可能小（因为若 T_{1,x}\in T_{1,n}，T_{1,x} 的分数小于等于 T_{1,n} 的分数，因此后手想让子游戏长度尽量小），即 y 肯定是选择相邻（即左右两侧分别离 x 最近的的问号） x 的一个问号。

同理，对于第 i 轮来说，把前 i-1 轮形成的序列看成原串，第 i 轮后手操作的问号也应该与先手操作的问号相邻,并且只需要考虑第 i 轮被先手操作的子游戏。

接下来，大概就能 dp 了。设 T 是这样的结构：a_1 个 0，？，a_2 个 0，?，\dots，a_m 个0。

不失一般性的，假设在第一轮过后，先手选择了 a_{k-1} 后的问号，后手选择了 a_{k} 后的问号，那么结构变为：a_1,a_2\cdots a_{k-2},a_{k-1}+a_{k}+1

我们紧接着来讨论第二轮先手的取值情况，

进一步考虑的话，我们发现我们不用去考虑先手第二轮操作 a_{p} 后问号，后手操作 a_{p+1} 后问号时的贡献( p \le k-3)：

:::info[证明]

先看怎么描述总体答案的:

ans=\max_{先手第一轮取 i 后的问号}(\min(后手第一轮取 i+1 后的问号，后手第一轮取 i-1 后的问号))

对于这个操作，我们发现贡献就相当于先手第一轮取 a_{p} 后的问号，后手取 a_{p+1} 后的问号。我们要讨论这个贡献会不会被这种情况贡献给 ans。

分类讨论两类大小的取值

当 a_1...a_{p}+a_{p+1}+1构成的子游戏 贡献小于等于由 a_{p}+a_{p+1}+1,a_{p+2}...a_n构成的子游戏 的贡献时，先手第一轮取 i 后的问号时，左边的子游戏会被贡献给 ans，即 a_1...a_{p}+a_{p+1}+1构成的子游戏 的贡献不必在第一轮先手选 a_{k-1} 下的情况讨论——会被先手第一轮选 a_{p} 的问号的情况贡献给 ans，

而当 a_{p}+a_{p+1}+1,a_{p+2}...a_n构成的子游戏 的贡献较小时，有不等式：

a_1...a_{p}+a_{p+1}+1构成的子游戏\\ >a_{p}+a_{p+1}+1,a_{p+2}...a_{k-1}+a_{k}+1构成的子游戏\\

由于 a_{p}+a_{p+1}+1,a_{p+1}...a_{k-1}+a_{k}+1构成的子游戏（操作完两轮后） 是 a_{p}+a_{p+1}+1...a_{n}构成的子游戏（操作完一轮后）中第二轮先手选择 a_{k-1} 后的问号，后手选择 a_{k} 后问号构成的局面。

可以推出：

a_{p}+a_{p+1}+1,a_{p+1}...a_{k-1}+a_{k}+1构成的子游戏\\ \ge a_{k-1}+a_{k}+1,...a_n 构成的子游戏

同时，第一轮先手选择 a_{k-1} 后的贡献恰好就是 \min(a_{1},a_{2}...a_{k-2}构成的子游戏,a_{k-1}+a_{k}+1,...a_n 构成的子游戏)，即：

a_{k-1}+a_{k}+1,...a_n 构成的子游戏 \ge 第一轮选择先手选择 a_{k-1} 后问号的贡献

回顾逻辑链，有：

a_1...a_{p}+a_{p+1}+1构成的子游戏\\ >第一轮选择先手选择 a_{k-1} 后问号的贡献

这说明 a_1...a_{p}+a_{p+1}+1构成的子游戏 一定不会在第一轮先手选择 a_{k-1} 后问号时被考虑到，也就不需要考虑其贡献。

a_1...a_{p}+a_{p+1}+1构成的子游戏\\ >a_{p}+a_{p+1}+1,a_{p+1}...a_{k-1}+a_{k}+1构成的子游戏\\ \ge a_{p}+a_{p+1}+1...a_{k-1}+a_{k}+1 构成的子游戏 \\

即在第一轮先手选择 a_{k-1} 后的问号，后手选择 a_{k} 后的问号，第二轮先手选择 a_{p} 后的问号时，后手由于会选取使得答案较小的问号因此后手一定会选择 a_{p-1} 后的问号。

综上，我们不需要考虑这种情况下的贡献。 :::

:::info[证明]

显然，我们需要满足先手第二轮操作 a_{p} 后问号时后手操作 a_{p+1} 后问号时的贡献大于后手操作 a_{p-1} 时问号的贡献。

我们假设在最优方案中第三轮先手操作 a_{q},q\in (p,k-1) 后的问号。我们可以立刻发现：

当我们第二轮先手操作 a_{q} 后的问号，后手操作 a_{q+1} 后的问号，第三轮先手操作 a_{p} 后的问号时，由于上面的条件限制，后手一定操作 a_{p-1} 后的问号。即：

a_{1}...a_{q}+a_{q+1}+1 构成的游戏\\ \ge a_{p}+a_{p+1}+1...a_{q}+a_{q+1}+1构成的游戏

然后我们分后手的操作讨论。

a_{p}+a_{p+1}+1...a_{q}+a_{q+1}+1构成的游戏\\ \ge a_{q}+a_{q+1}...a_{k-1}+a_{k}+1构成的游戏

根据逻辑链，有：

a_{1}...a_{q}+a_{q+1}+1 构成的游戏\\ \ge a_{q}+a_{q+1}...a_{k-1}+a_{k}+1构成的游戏

即我们当第二轮先手选择 a_{q} 后的问号时，后手也会选择 a_{q-1} 后的问号。

a_{q}+a_{q+1}...a_{k-1}+a_{k}+1构成的游戏\\ \ge a_{p}+a_{p+1}+1...a_{q}+a_{q+1}+1 构成的游戏

同时，根据逻辑链，有：

a_{1}...a_{q}+a_{q+1}+1 构成的游戏\\ \ge a_{p}+a_{p+1}+1...a_{q}+a_{q+1}+1构成的游戏

这意味着，当第二轮先手选择 a_{q} 后的问号时，后手的两个选择都比第三轮的两个选择优。因此我不如第二轮先手选择 a_{q} 后的问号。

即第二轮选 a_{q} 后的问号比第二轮选 a_{p} 后的问号不劣，再进行归纳论证，得证。 :::

(主播可能证烦了，有简单的证明可以和主播说，证明应该是没有大问题的)

:::warning

对于先手操作 a_{k-3} 后问号的情况，还需要根据后手的情况比较取最小值。 :::

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n;
string s;
int pre[N],nxt[N];
int calc(vector<int>vt)
{
    int res=0;
    for(int i=0;i<vt.size();i++)res=max(res,vt[i]),pre[i]=nxt[i]=0;
    for(int i=0;i<(int)vt.size()-1;i++)res=max(res,vt[i]+vt[i+1]+1);
    for(int i=1;i<(int)vt.size()-2;i++)
    {
        pre[i]=vt[i+1]+vt[i]+vt[i-1]+2;
        if(i>=2)pre[i]=max(pre[i],min(vt[i-2]+vt[i-1]+vt[i]+vt[i+1]+3,pre[i-2]));
    }
    for(int i=(int)vt.size()-3;i>=1;i--)
    {
        nxt[i]=vt[i]+vt[i+1]+vt[i+2]+2;
        if(i+3<vt.size())nxt[i]=max(nxt[i],min(vt[i]+vt[i+1]+vt[i+2]+vt[i+3]+3,nxt[i+2]));
        res=max(res,min(pre[i],nxt[i]));
    }
    return res;
}
void solve()
{
    cin>>s;n=s.length();s=" "+s;
    vector<int>vt;
    int ans=0,res=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1'){vt.push_back(res),ans=max(ans,calc(vt)),res=0,vt.clear();}
        else if(s[i]=='?'){vt.push_back(res);res=0;}
        else res++;
    }
    vt.push_back(res),cout<<max(ans,calc(vt))<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _;cin>>_;while(_--)solve();
    return 0;
}

:::

方法 2.

闭眼考虑二分。即二分 x 表示最终游戏结束时是否存在一个大于等于 x 的 0 区间。

显然先后手只关心问号，那么我们把问号抽出来构成一个序列，并预处理出来互不包含的区间，每个区间表示若先手取到了这里面的全部问号，那么就会形成一个长度大于等于 x 的区间。

因此，我们的博弈转到了：先手是否存在一种操作，使得至少存在一个区间里的问号全被先手选中。

那么我们分类讨论区间的情况：

将所有问号按顺序两两配对，当先手选择一个问号时，后手选择一个与之匹配的问号。这样可以保证每对问号至少有一个位置为 1。那么由于每个区间长度大于等于 3，那么每个区间至少包含一对问号，即每个区间里面至少有一个问号被改为 1。

这样先手一定构造不出来合法答案。

对于一个长度为 2 的区间，若先手选择了其中一个问号，后手一定需要选择另一个问号。因此先手可以采取先操作这种长度为 2 的区间里的问号的方法。

那么如果其他区间和这个区间有交，那么这个区间的一部分已经被确定了。

  1. 两个长为 2 的区间有交且交大小为 1。那么：先手可以操作交集的那个问号，后手只能在左右两个问号里选择一个。无论后手怎么选，左右两个问号总会剩一个，先手选择这个问号即可，即此种情况下先手必胜

  2. 一个区间长为 2，一个区间长为 3，交集为 1：先手选择交集所在的那个问号，后手必然选择长度为 2 区间的另一个问号，这时候长度为 3 的区间相当于被缩短成了一个长为 2 的区间。

由于上述讨论把所有情况都覆盖到了，上面的操作大概率是对的。

:::info[证明]

还是考虑问号匹配的构造，如果两个问号之间先手选择一个时后手必须选择另一个时，将这两个问号配对。同时，若一个区间包含一对匹配项，那么这个区间至少含有 1，一定不合法。

如果不停执行上面的操作 2 能够推出 1 操作，此时那么先手胜利，先手只需要按上面描述的操作实现即可。此时由于存在一操作，此时会存在一个问号同时属于两组配对。

如果推不出 1 操作，那么在当前的配对情况下不存在一个问号同时属于两组配对。那么我们进行如下操作：对于目前形成的配对的情况下，把已经包含匹配问号的区间删掉。同时，将区间范围缩小至满足区间内不包含已匹配问号。

（这样的修改操作对后手不利，若我们能说明在这种情况下先手仍然必输，则能说明在原局面下先手必输）

我们略微讨论下缩小区间的情况：

接着，我们按已匹配的问号将序列问号划分成若干段，且每一段全都是未被匹配的括号。修改完后的区间只存在于某一段中。同时，有：

那么，看成若干个子游戏，若先手选择某个子游戏进行操作，那么后手紧跟在先手也在这个子游戏进行操作，并且对每个子游戏分别构造策略：

综上，先手必输，得证。 :::

那么问题就相当于对于先手，对于长度为 2 的区间，如何放置。

那么再分析一下，除去一些直接判断的情况（存在长度为 1 的区间，区间长度全部大于等于 3），我们只需要观察，对于任意两个相邻的长度为 2 的区间，是否能构造出胜利策略即可。

那么，我们从左往右扫描，对于当前长度为 2 的区间，如果先手放右侧能直接推出胜利，那么放右侧；否则先手希望放左侧在未来的扫描中能推出胜利。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n;
string s;
int id[N],nxt[N],pre[N];
int calc(int l,int r,int i,int j){return min(r,nxt[j]-1)-max(l,pre[i]+1)+1;}
int check(int l,int r,int x,int st)
{
    if(r-l+1<x)return 0;
    if(st>r)return 1;
    int nowl=0,nowr=0;
    for(int i=st,j=i;i<=r;i=nxt[i])
    {
        while(j<i)j=nxt[j];
        while(j<=r&&calc(l,r,i,j)<x)j=nxt[j];
        if(j>r)break;
        int tl=id[i],tr=id[j];
        if(tl>=tr)return 1;
        else if(tr-tl+1==2)
        {
            if(nowr==tl)return 1;
            else nowl=tl,nowr=tr;
        }
        else if(tr-tl+1==3)
        {
            if(nowr==tl)nowl=tl+1,nowr=tr;
        }
    }
    return 0;
}
int check(int x)
{
    int l=0,st=0;
    for(int i=1;i<=n;i++)
        if(s[i]=='1')
        {
            while(st<l+1)st=nxt[st];
            if(check(l+1,i-1,x,st))return 1;
            l=i;
        }
    while(st<l+1)st=nxt[st];
    return check(l+1,n,x,st);
}
void solve()
{
    cin>>s;n=s.length();s=" "+s;
    int p=0,cnt=0;
    for(int i=0;i<=n+1;i++)id[i]=nxt[i]=pre[i]=0;
    for(int i=1;i<=n;i++)if(s[i]=='?')id[i]=++cnt,nxt[p]=i,pre[i]=p,p=i;
    nxt[p]=n+1,pre[n+1]=p;
    int l=0,r=n,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)){ans=mid,l=mid+1;}
        else r=mid-1;
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _;cin>>_;while(_--)solve();
    return 0;
}
/*
1
00?00?100?0
*/

:::

E

:::info[题面]

我们需要保证对于每种车站 y 的取值方案都能满足限制，聚焦于同一等级 x 的车站，一个较为显然的直觉是：只需要关注最左边和最右边的车站是否联通即可。(不会的可以问 AI，懒得证了)

那么我们记等级为 x 的车站中最左端的位置为 lm_x，最右端为 rm_x。

再来考察单个列车 i 能覆盖掉那些等级的车站的需求：

对于第一种讨论，我们只需要知道 \min_{所有列车}(\max(x_i,y_i)) 即可，跟 p,lm_i,rm_i 没有关系。

满足第二种讨论的车站等级是固定的，这部分我们可以先预处理掉。

对于第三种讨论，我们可以看成一个前缀的形式，即对于某个等级 x，所有 p_i\le lm_i 的列车里至少有一个车站的 y\le x。

那么，接下来的思路就清晰了，我们先用容斥（或者 DP 额外记一维）把第一种讨论的限制去掉：

假设我们要求 \min_{所有列车}(\max(x_i,y_i))=v 的答案。那么在去掉所有等级大于等于 v 的车站后，写成如下形式： \min(\max(x_i,y_i))\ge v 的答案减去 \min(\max(x_i,y_i))> v 的答案。

:::warning[注意] 不能直接化成\min(\max(x_i,y_i))\ge v 的答案减去 \min(\max(x_i,y_i))> v 的答案，因为此时两种情况的车站种类不同，和 v 的限制不同，两个维度不同不能直接相减。所以我们先要固定通过第一种讨论的车站种类来减少一个维度。 :::

然后就是对第三种讨论技术了，这是个 naive 的 DP，我是这么实现的：

把车站按 p 排序，并预先处理 mn_i 表示 \forall i,lm_i\le i,\min(i)，并设 dp_{i,j} 表示从前往后 DP 到了第 i 个列车，前 i 个列车的 y 的最小值为 j 的方案数。

那么对于一步转移 dp_{i,j}\to dp_{i+1,\min(j,k)}，我们要保证 \forall q,lm_q\in [p_i,p_{i+1}),q\le j。

由于 dp_{i,j} 合法，那么可以推出前 i 俩列车的最小值小于等于 \forall q,lm_q\le p_i,\min(q)，即 j\le mn_{p_i}。

合起来就是限制：j\le mn_{p_{i+1}-1} 。实现的时候可以在枚举 k 的时候直接把 k 的限制也判掉。另外，还要满足 \min(x_{i+1},k)\ge v 或 \min(x_{i+1},k)>v。

显然满足条件的 k 可以连续的分为两类不同的贡献，前缀和和差分优化即可。

那么总的复杂度就是：O(nk^2)。

:::info[代码]

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod=998244353,N=1e3+10,M=510;
int n,m,k;
int a[N],pl[N],pr[N];
//pl[i] 和 pr[i] 表示等级为 i 的车站的最左端和最右端位置，没有为 0
vector<int>g[N];
int dp[N][M],mn[N],t[N];
struct Node{int p,x;Node(int p=0,int x=0):p(p),x(x){}}p[N];
int power(int x,int y,int t=1){for(;y;y>>=1,x=x*x%mod)if(y&1)t=t*x%mod;return t;}
int calc(int k0,int lim)
//只考虑 <=k0 的车站，要求 \min(\max(x_i,y_i))>=lim
{
    for(int i=0;i<=n;i++)mn[i]=lim;
    for(int i=1;i<=k0;i++)if(pl[i])mn[pl[i]]=min(mn[pl[i]],i);
    for(int i=1;i<=n;i++)mn[i]=min(mn[i],mn[i-1]);
    if(mn[p[1].p]<lim)return 0;//1~p[1].p-1 并没有列车覆盖
    for(int i=0;i<=m;i++)for(int j=1;j<=lim;j++)dp[i][j]=0;
    dp[0][lim]=1;
    // for(int i=0;i<m;i++)for(int j=1;j<=lim;j++)if(dp[i][j])
    //     for(int nxt=(p[i+1].x>=lim?1:lim);nxt<=k;nxt++)
    //         if(mn[p[i+2].p]>=min(nxt,j))
    //             (dp[i+1][min(nxt,j)]+=dp[i][j])%=mod;
    //O(nk^2) 暴力
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<=lim;j++)t[j]=0;//t 记录差分数组
        for(int j=1;j<=lim;j++)if(dp[i][j])
        {
            int l=1,r=k;
            if(p[i+1].x<lim)l=lim;
            if(j>mn[p[i+2].p])
            {
                r=min(r,mn[p[i+2].p]);
                if(l<=r)(t[l]+=dp[i][j])%=mod,(t[r+1]+=mod-dp[i][j])%=mod;
            }
            else 
            {
                (dp[i+1][j]+=(r-max(l,j)+1)*dp[i][j])%=mod;
                if(l<j)(t[l]+=dp[i][j])%=mod,(t[j]+=mod-dp[i][j])%=mod;
            }
        }
        for(int j=1;j<=lim;j++)(t[j]+=t[j-1])%=mod,(dp[i+1][j]+=t[j])%=mod;
    }
    int res=0;for(int j=1;j<=lim;j++)(res+=dp[m][j])%=mod;
    // cout<<k0<<' '<<lim<<" "<<res<<endl;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];pr[a[i]]=i;
        if(!pl[a[i]])pl[a[i]]=i;
    }
    for(int i=1;i<=m;i++)cin>>p[i].p>>p[i].x;
    sort(p+1,p+m+1,[&](const Node&x,const Node&y){return x.p<y.p;});
    for(int i=1;i<=k;i++)if(pr[i])g[pr[i]].push_back(i);
    int mn=k+1;for(int i=n,j=m;i>=1;i--)//第二类讨论
    {
        while(j>=1&&p[j].p>=i){mn=min(mn,p[j].x);j--;}
        for(auto x:g[i]){if(x>=mn||pl[x]==pr[x])pl[x]=pr[x]=0;}
        g[i].clear();
    }
    int ans=0;
    p[m+1].p=n;
    for(int i=1;i<=k;i++)ans=(ans+mod+calc(i-1,i)-calc(i-1,i+1))%mod;
    cout<<ans<<endl;
    return 0;
}

:::

F

:::info[题面]

记 [l,r] 表示区间 l 到 r。称一个由区间作为元素构成的集合 S 是青的，当且仅当：

对于所有青的集合 S，求 \sum q^{|S|} \bmod 998244353。

n\le 10^5,1\le q <998244353

:::

假设我们已经会了这道题，我们来看看这道题怎么做。

性质

首先来发掘一些特殊性质：

这种情况给了我们一些提示：

这说明如果我们能处理左端点在 x 的区间，那么可以以某种分治的方式进行 DP。显然，左端点在 x 的区间会受被 [R_x,n] 包含的区间的影响，我们有理由相信，左端点在 x 的区间和左端点在 R_x 的区间有某种神秘的联系。

区间 2 和 3 可以推出区间 4，区间 1 和区间 4 可以推出区间 5。即若 [x,r_1],[R_x,r_0] 在 S，且 r_1\ge r_0，则 [x,r_0] 也在 S。即 S_x/\{x\} 是 S_{R_x} 的一个前缀。

假设我们已经确定了所有被 [R_x,n] 包含的区间，感受一下，上面的讨论应该已经确定了左端点为 x 的区间的所有情况。

:::info[证明] 首先，一个合法的左端点为 x 的区间的取法一定满足上面所给的条件，我只需要说明：Sr_x/\{x\} 任取 Sr_{R_x} 的前缀所构成的集合 S 都满足题目的限制即可。

显然，我们只需要关注新加的 Sr_x 带来的变化即可，即对于任意 [x,r] 和 [a,b] 满足 x\le a<r\le b，[x,a] 和 [r,b] 都已经在集合 S 内即可：

首先，由于 a\ge R_x，可以推出 [R_x,r] 已经和 [a,b] 构成了 [R_x,a] 和 [r,b]。那么 [R_x,a] [r,b] 已经存在了；同时，因为 ：Sr_x/\{x\} 是 Sr_{R_x} 的一个前缀，那么有 [x,a] 已经在 S 内了。

因此假设成立。 :::

DP

虽然推性质有点难。不过之后我们可以设计出一个复杂度较高的 DP 了。

我们记 F_{i,j} 表示在只考虑 l,r\in[0,i-1] 的情况下，|R_0/\{x\}|=j 时候 q^{|S|} 的和。 （j<i） 考虑初值：

F_{0,0}=0，F_{1,0}=1

（长度为 1 的时候只有 [0,0] 一个区间。长度为 0 的时候我们先规定不合法）

再看递推式子：

f_{i,0}=\sum_{j=0}^{i-2}f_{i-1,j},i>1\\ f_{i,j}=q^{j}\sum_{0< k<i}f_{i-k,0}\sum_{l\ge j-1}f_{k,l},j\ge 1

答案即 q^{n+1}f_{n+2,0}。其中 q^{n+1} 是为了补上未计算的 n+1 个 [i,i] 的区间。f_{n+2,0} 即我们强制在原序列最左侧加了一个只有区间长度为 1 的点方便统计。(原本题目中序列长度为 n+1)

化简

接下来就该数学大手子发力了。

我们考虑把 f_{i,j} 写成生成函数的形式，由于第二条式子中 i 这一维很像卷积，那么我们不妨设：

G_j(x)=\sum_{i\ge 0}f_{i,j}x^i

那么重写上面的式子：

G_0(x)=x+x\sum_{j\ge 0}G_j(x)\to G_0(x)=\frac{x+x\sum_{j>0}G_j(x)}{1-x}

（递推时要补上 [x^1]G_0(x) 的贡献）

G_j(x)=q^jG_0(x)\sum_{l\ge j-1}G_l(x)\\ ans=q^{n+1}[x^{n+2}]G_0(x)

下面给出推式子的两种方法：

:::info[方法1]

既然涉及到 \sum_{l\ge j-1}G_l(x)，那么我们的思路转为从无限项推出 G_1 和 G_0。由此，我们设 S_j(x)=\sum_{l\ge j}G_l(x)，那么有：

G_0(x)=\frac{x(1+S_1(x))}{1-x}\to S_1(x)=\frac{(1-x)G_0(x)}{x}-1\\ S_{j}(x)-S_{j+1}(x)=q^{j}G_0(x)S_{j-1}(x)\to \\ S_{j+1}=S_j(x)-q^{j}G_0(x)S_{j-1}(x)

写成比值的形式，可以发现有相邻项比值的关系，即：

\frac{S_{j+1}}{S_j}=1-\frac{qG_0}{S_{j-1}/S_j}

那么设 R_j(x)=\frac{S_{j+1}}{S_j}，我们希望用 R_{j} 来表示 R_{j-1}：

R_j(x)=1-\frac{q^jG_0}{R_{j-1}(x)}\to\\ R_{j-1}(x)=\frac{q^{j}G_0}{1-R_{j}(x)}

取 j=1，再把 R_j(x) 项无限展开：

\frac{S_1}{S_0}=\frac{qG_0}{1-R_1(x)}\\ =\frac{qG_0}{1-\frac{q^2G_0}{1-...}}

可以看出，化成了类似连分数的形式。我们采用一个弱智小技巧，设 Q(G_0)=R_0，由于始终只涉及到 G_0 的零次项和一次项，那么有：

Q(G_0)=\frac{qG_0}{1-Q(qG_0)}

那么根据解析式我们可以较轻松的求出 Q(x)=\frac{qx}{1-Q(qx)}，怎么求先按下不表。

那么可以化出等式：

\frac{S_1}{S_0}=\frac{\frac{(1-x)G_0(x)}{x}-1}{G_0+\frac{(1-x)G_0(x)}{x}-1}\\ =\frac{(1-x)G_0(x)-x}{G_0(x)-x}=1-\frac{xG_0(x)}{G_0(x)-x}=P(G_0)\\

那么，设 G_0(x)=z，有：

1-xz/(z-x)=Q(z)\\ z-x-xz=zQ(z)-xQ(z)\\ z(1-Q(z))=x(1+z-Q(z))\\ \frac{z(1-Q(z))}{1+z-Q(z)}=x

那么，我们设函数 SB(x)=\frac{x(1-Q(x))}{1+x-Q(x)}，只需要求出满足 SB(G_0(x))=x 的 G_0(x) 即可，即求 SB 的复合逆。

不过，为了方便讲解，我们统一一下形式：设 P(x)=\frac{x}{1-P(qx)}。那么显然有等式 P(qx)=Q(x)，那么带入 P(x)，有：

P(x)=\frac{x}{1-Q(x)}\to Q(x)=1-\frac{x}{P(x)}

再带入 \frac{z(1-Q(z))}{1+z-Q(z)}=x，有：

\frac{z}{P(z)+1}=x

::: :::info[方法2]

G_0(x)=\frac{x+x\sum_{j>0}G_j(x)}{1-x}\\ G_j(x)=q^jG_0(x)\sum_{l\ge j-1}G_l(x)

由于递推方程式中带个 G_0(x)，我们有理由猜测 G_j(x) 能表示成关于 G_0(x) 的多项式。

考虑 G_1(x) 的取值：

\sum_{l\ge 0}G_l(x)=\frac{G_0(x)}{x}-1\\ G_1(x)=qG_0(x)\sum_{l\ge 0}G_l(x)=qG_0(x)\frac{G_0(x)-x}{x}\\ =q\frac{G_0^2(x)}{x}-qG_0(x)

我们发现，主播主播，这也不能啊？但题解就是这么写的呀？。好吧，其实不需要这么麻烦，我们可以肉眼看出 [x^0]G_0(x)=0,[x^1]G_0(x)=1，即 G_0(x) 在形式幂级数意义下存在多项式复合逆（注：这并非充要条件），即存在 F(x) 使得 F(G_0(x))=x，那么显然任意一个多项式都可以表示成以 G_0 为自变量的多项式。

那我们设 G_j(x)=H_j(G_0(x))， 那么有：

H_j(z)=q^{j}z\sum_{l\ge j-1}H_l(z)\\ H_0(z)=z

由于我们要求：

G_0(x)=\frac{x+x\sum_{j>0}G_j(x)}{1-x}

因此，我们设 P(z)=\sum_{j\ge 0}H_j(z)，我们只需要求出 P(z) 就能表示出 G_0(x)：

我们可以思考 H_j(z)=q^{j}z\sum_{l\ge j-1}H_l(z) 的几何意义：对于一条路径，我们发现每次转移时固定增加一个 z，在多一个 z 时原本所处的 H_l(z) 可以转移到任意一个 1\le j\le l+1 的 H_j(z)。那么可以翻译成以下的组合问题：

从 (1,0) 开始（因为不存在 H_j(z) 有 0 次项，只有 H_0(z) 有一次项，其中 (i,j) 表示走到了 [z^i]H_j(z) 这一项上），每次向右走一步，最多向上走一步，可以向下走任意步（不能碰到 y=0 的位置），。一个路径（(x_1=1,y_1)\to (x_2=2,y_2)...(x_m=m,y_m)）的权值为 q^{\sum_{i=1}^{m}y_m}。那么 [z^m]P(z) 就是所有从 (1,0) 走到 (m,j)（j\ge 1） 的路径的权值之和。

对于一条路径，考虑抽出所有满足 y=1 的横坐标 p_1=1,p_2...p_k。那么显然对于 i\in(p_i,p_{i+1}),y_i>1，那么我们可以推出 y_{p_{i}+1}=y_{p_i}+1，（因为 y_{p_i}=1）且对 y_{p_{i+1}-1} 并没有做出什么限制，这说明我们可以将 i\in(p_i,p_{i+1}) 的 y 坐标统一减一后，这可以看作一个子问题，然后对于子问题中的每一条路径，放回到原来的问题时要额外乘上 q^{p_{i+1}-p_{i}-1}。

那么我们尝试用 P(z) 来表示递推式：我们枚举 p_1...p_k 的 k 的大小，实际上我们不关系 p_1..p_k 的大小，我们只关心求出被分成的 k 个子问题的长度之和加上 k 恰好等于 m（[z^m]P(z)) 即可，这可以用卷积表示。而对于每一个子问题，若他的长度为 o，我们希望给他乘上 q^{o} 的系数，那么我们发现我们可以用 P(qz) 来实现乘上 q^{长度} 的这个需求。那么综上，有递推式：

P(z)=\sum_{i=1}^{+\infin}z^{i}P^{i}(qz)\to P(z)=\frac{z}{1-P(qz)}

因为 P(G_0)=\sum_{j>0}G_j(x)，带回到 G_0(x)=\frac{x+x\sum_{j>0}G_j(x)}{1-x}，有：

G_0(x)=\frac{x(1+P(G_0(x))-G_0(x))}{1-x}\\ G_0=x(1+P(G_0))\to x=\frac{G_0}{1+P(G_0)}\\

那么设 F(x)=\frac{x}{1+P(x)}，只需要求出 F(x) 的复合逆即可。 ::: 综上，我们可以推出：

P(x)=\frac{x}{1-P(qx)}\\ \frac{G_0}{1+P(G_0)}=x

只要完成求解就能完成主人的任务了！

求解 P(x)=\frac{x}{1-P(qx)}

下面给出三种求解 P(x) 的方法，复杂度分别是 O(n\log^2n),O(n\log n),O(n\log n)。

:::info[方法1：全在线卷积] 变形式子 P(x)(1-P(qx))=x\to P(x)=x+P(qx)P(x)，那么使用全在线卷积求解 P(x)：

设 p_i=[x^{i}]P(x),g_{i}=q^{i}p_i，P(0)=0\to q_0=p_0=0,p_1=1，式子为：

p_i=\sum_{i=0}^{n}p_ig_{n-i}=\sum_{i=1}^{n-1}p_ig_{n-i},i>1

我们用函数 solve(l,r) 表示已经求解了 p_{0...l-1} 现在要求解 p_{l...r} ，并且设 f_i 表示：f_i=\sum_{j=1}^{i-1}[j<l\And i-j<l]p_jg_{n-j}，即所有下标小于 l 的 p 和 g 对 p_{l...r} 的贡献的和。

  • 边界情况：l=r\to p_i=f_i,g_i=qp_i。

    那么设 mid=\lfloor \frac{l+r}{2}\rfloor，我们先调用 solve(l,mid) 求出 p_{l...mid}，再考虑更新 f 数组并递归到 solve(mid+1,r)。即：

    i\in[mid+1,r],f_{i}=\sum_{j=l}^{mid}[i-j\le mid]p_jg_{i-j}+\\ \sum_{j=l}^{mid }[i-j<l]g_{j}p_{i-j}

    即我们构造如下序列进行卷积并求和即可：

  • 可以看出，上述序列的大小均为 $O(r-l)$，因此可以套用主定理进行分析，复杂度 $O(n\log^2n)$。 :::

::::info[方法 2：神秘数学技巧]

\frac{F(qx)}{F(x)}=\frac{1}{1-qxF(q^2x)/F(qx)}\\ \to F(qx)-qxF(q^2x)=F(x)\\

那么设 f_i=[x^i]F(x)，有：

q^{i}f_i-q^{2i-1}f_{i-1}=f_i\\ \to (q^{i}-1)f_i=q^{2i-1}f_{i-1}\\ \to f_i=\frac{q^{2i-1}}{q^{i}-1}f_{i-1}\\

那么如果 q\not =1\And q\not =-1，我们可以线性求出 F(x)，并使用多项式求逆求出 P(x)。那么讨论一下特殊情况：

P(x)=\frac{x}{1-P(x)}\to P^2(x)-P(x)+x=0\\ P(x)=\frac{1\pm\sqrt{1-4x}}{2}\\

有两个解，我们带一下特殊值：P(0)=0，可以看到：P(x)=\frac{1+\sqrt{1-4x}}{2}。对于 \sqrt{1-4x}，我们有若干种求解办法：

:::info[方法1：牛顿二项式展开]

(1-4x)^{\frac{1}{2}}=\sum_{i=0}^{+\infin}\binom{\frac{1}{2}}{i}(-4)^{i}x^{i}

:::

:::info[方法2：求导高手]

设 y=\sqrt{1-4x}，那么：

\ln y=\frac{1}{2}\ln(1-4x)\\

两边求导，可得：

y=\frac{4x-1}{2}y'

我们设 y=\sum_{i\ge 0}b_ix^{i}\to y'=\sum_{i\ge 0}(i+1)b_{i+1}x^{i}，那么有：

b_{i+1}=\frac{2(2i-1)b_i}{i+1}

（注意手算 b_0 和 b_1，不会算可以用牛顿二项式展开算，因为上面求解过程涉及到求导会丢项）

回带到 P(x)，有：（q=1）

p_0=0,p_1=1,p_i=\frac{4i-6}{i}p_{i-1}

同理，当 q=-1 时，有：

P(x)P(-x)-P(x)+x=0\\

由于 P(-x)=\frac{-x}{1-P(x)}，可以推出：

P^2(x)-(1+2x)P(x)+x=0

同理，可以推得：

p_0=0,p_1=1,p_2=-1,p_i=\frac{12-4i}{i}p_{i-2}

::: 那么，我们能手动推出来 q=1 和 q=-1 的时候的递推式子：

::::

::::info[方法 3：连分数递推]

观看 OI wiki 上关于连分数的前一部分教程，用于主播在学多项式，我们只讨论形式幂级数下的连分数。那就开始今天的红色沙漠连分数大学习吧。

:::info[基础知识] 具体来说，如果一个形式幂级数 f(x) 被展开为如下形式的连分数：

f(x) = a_0(x) + \cfrac{b_1(x)}{a_1(x) + \cfrac{b_2(x)}{a_2(x) + \cfrac{b_3(x)}{a_3(x) + \ddots}}}

一般记为：f(x) = [a_0(x); (b_1(x), a_1(x)), (b_2(x), a_2(x)), \dots]。

其中 a_n(x) 和 b_n(x) 是 x 的多项式，那么，它的第 n 阶渐进分数 C_n(x) 定义为截取该连分数的前 n+1 项（从 a_0 到 a_n）得到的有限连分数的值：

C_n(x) = a_0(x) + \cfrac{b_1(x)}{a_1(x) + \cfrac{b_2(x)}{a_2(x) + \cfrac{\ddots}{ \ddots + \cfrac{b_n(x)}{a_n(x)}}}}
显然，C_n(x) 只涉及到初等运算，因此 C_n(x) 总可以表示成关于 \frac{A_n(x)}{B_n(x)} 的形式，其中 A_n(x) 和 B_n(x) 都是多项式。并且可以根据归纳法求出 A_n(x) 和 B_n(x)： 序列 递推公式 (n \ge 1) 初始条件 (通常设定)
分子 A_n(x) A_n(x) = a_n(x) A_{n-1}(x) + b_n(x) A_{n-2}(x) A_0(x) = a_0(x)
分母 B_n(x) B_n(x) = a_n(x) B_{n-1}(x) + b_n(x) B_{n-2}(x) B_0(x) = 1

证明如下：

现在我们看 C_{k+1}。根据连分数的定义：

C_{k+1} = a_0 + \cfrac{b_1}{a_1 + \cfrac{\ddots}{a_{k-1} + \cfrac{b_k}{a_k + \cfrac{b_{k+1}}{a_{k+1}}}}}

那么可以看作：

C_{k+1} = a_0 + \cfrac{b_1}{a_1 + \cfrac{\ddots}{a_{k-1} + \cfrac{b_k}{a'_k}}}

，即 C_{k+1} = [a_0; (b_1, a_1), \dots, (b_k, a'_k)] 其中 a'_k=a_k+\frac{b_{k+1}}{a_{k+1}}。那么，根据归纳法，有：

C_{k+1}=\frac{a'_kA_{k-1}+b_kA_{k-2}}{a_k'A_{k-1}+b_{k}B_{k-2}}\\ = \frac{a_{k+1} (a_k A_{k-1} + b_k A_{k-2}) + b_{k+1} A_{k-1}}{a_{k+1} (a_k B_{k-1} + b_k B_{k-2}) + b_{k+1} B_{k-1}}=\frac{A_{k+1}}{B_{k+1}}

综上，归纳成立。

同时，为了进行误差分析，即为了考察 C_{n}-C_{n-1}=\frac{A_{n}B_{n-1}-A_{n-1}B_{n}}{B_nB_{n-1}} 的大小，我们记 D_{n}=A_{n}B_{n-1}-A_{n-1}B_{n}，并考察 D_n 的递推式：

D_n=(a_nA_{n-1}+b_nA_{n-2})B_{n-1}-A_{n-1}(a_nB_{n-1}+b_nB_{n-2})\\ =-b_n(A_{n-1}B_{n-2}-A_{n-2}B_{n-1})\\ D_1=b_1\to D_n=(-1)^{n-1}\prod_{i=1}^{n}b_i

::: 那么，根据 P(x) 的函数写成连分数的形式：

P(x)=\cfrac{x}{1-\cfrac{qx}{1-\cfrac{q^2x}{\ddots}}}

那么有：

a_0=0,a_i=1,b_i=-q^{i-1}x\\ A_0=0,A_1=x,B_0=1,B_1=1\\ A_i=A_{i-1}-q^{i-1}xA_{i-2}\\ B_i=B_{i-1}-q^{i-1}xB_{i-2}\\

并且根据递推式子我们可以反推复合条件的 A_{-1}=-1,B_{-1}=0。

我们发现在一类特殊的形式幂级数下，我们可以采用 C_n 在 \bmod x^{n} 意义下逼近原连分数，以 P(x) 为例：

|C_n-C_{n-1}|=\frac{|\prod_{i=1}^{n}b_i|}{B_{n}B_{n-1}}=\frac{q^{\frac{n(n-1)}{2}}x^{n}}{B_{n}B_{n-1}}

根据上面的递推式，取 [x^0] 有：[x^0]B_i=[x^0]B_{i-1}，因此，[x^0]B_i=1。即 B_i 存在乘法逆元，即 B_i=1+O(x)。因此：

原式=\frac{q^{\frac{n(n-1)}{2}}x^{n}}{B_{n}B_{n-1}}=O(x^{n})

即 C_n\equiv C_{n-1}\pmod {x^{n}}，因为是在形式幂级数下分析，有：\lim_{n\to +\infin}C_n=P(x)，即可以推出 C_{n}\equiv P(x)\pmod x^{n}。

注：如果你知识扎实的话，可以发现 [x^0]F\not =0 是 F 存在乘法逆元的充要条件，并且除上 F 可以看作乘上 F 的乘法逆元，并且可以如此构造出来：

[x^0]F^{-1}=1\\ \sum_{j=0}^{i}[x^j]F_j[x^{i-j}]F^{-1}=0,i>0\\ \to [x^i]F^{-1}=-\frac{1}{[x^0]F}\sum_{j=0}^{i-1}[x^j]F^{-1}[x^{i-j}]F

那么你自然就可以发现：两个多项式相除 \frac{A}{B}，如果 B 存在逆元，那么 \frac{A}{B} 的最低次幂和 A 的最低次幂相同。

综上，我们只需要求解 A_n 和 B_n 即可。可以把 A_n 和 B_n 看成矩阵乘法转移的形式：

\begin{pmatrix} A_i \\ A_{i-1} \end{pmatrix} = \begin{pmatrix} 1 & -q^{i-1}x \\ 1 & 0 \end{pmatrix} \begin{pmatrix} A_{i-1} \\ A_{i-2} \end{pmatrix}

那么设 M_{i}(x)=\begin{pmatrix} 1 & -q^{i}x \\ 1 & 0 \end{pmatrix} ，那么我们需要求出 \prod_{i=(n+2)-1}^{0}M_i(x)。考虑模仿类似矩阵快速幂的方式进行求解：

设 M(x,n)=\prod_{i=n-1}^{0}M_i(x)，那么考虑如何求出 M(x,2n)：

M(x,2n)=M(q^{n}x,n)\times M(x,n)

而实际上对于矩阵内的每一项元素，都有如下关系： [x^m]M(q^{n}x,n)=q^{nm}[x^m]M(x,n)。那么我们只用 M(n,n) 所产生的矩阵求出 M(x,2n)。那么就可以倍增了。最后，由于是逼近，我们可以直接求 A_{2^{k}},B_{2^{k}}（2^{k}\ge n+2）的答案，也即直接求转移矩阵的 2^k 幂即可。那么，可以看出：

\begin{pmatrix}A_{2^k}\\A_{2^{k}-1}\end{pmatrix}=(\prod_{i=2^{k}-1}^{0}M_i)\begin{pmatrix}A_{0}=0\\A_{-1}=-1\end{pmatrix}\to A_{2^k}=-(\prod_{i=2^{k}-1}^{0}M_i)[0][1] \begin{pmatrix}B_{2^k}\\B_{2^{k}-1}\end{pmatrix}=(\prod_{i=2^{k}-1}^{0}M_i)\begin{pmatrix}B_{0}=1\\B_{-1}=0\end{pmatrix}\\\to B_{2^{k}}=(\prod_{i=2^{k}-1}^{0}M_i)[0][0]

那么 P(x)=\frac{A_{2k}}{B_{2k}}\pmod x^{n+2}，求逆即可。 ::::

求解复合逆

算出 P(x) 以后，我们设 F(x)=\frac{x}{P(x)+1}，那么有：F(G(x))=x，然后我们需要求出 [x^{n+1}]G(x)，可以使用拉格朗日反演求解，不会的小伙伴可以参考[这篇博客]((´∇｀) 欢迎回来！) 和 这篇博客 进行学习，依照拉格朗日的式子，有：

[x^{n+2}]G(x)=\frac{1}{n+2}[x^{-1}]F^{-(n+2)}\\ =\frac{1}{n+2}[x^{n+1}](P(x)+1)^{n+2}

实现

下面给出根据三种方式求解 P(x) 的主代码：（头可以在 jiangly算法模板收集 - hh2048 - 博客园 里的多项式 Poly with Z 中找到，直接粘贴在上面即可）

:::info[方法一]

const int mod=998244353;
Z Inv(Z x){return power(x,mod-2);}
int n,q;
Poly p,f,g;
void solve(int l,int r)
{
    if(l==r)
    {
        p[l]=f[l],g[l]=power(Z(q),l)*p[l];
        return;
    }
    int mid=(l+r)>>1;
    solve(l,mid);
    Poly A,B,C;A.resize(mid-l+1),B.resize(min(mid,r-l)+1);
    for(int i=0;i<A.size();i++)A[i]=p[i+l];
    for(int i=0;i<B.size();i++)B[i]=g[i];
    C=A*B;
    for(int i=mid+1;i-l<C.size()&&i<=r;i++)f[i]+=C[i-(l)];
    A.resize(mid-l+1),B.resize(min(l-1,r-l)+1);
    for(int i=0;i<A.size();i++)A[i]=g[i+l];
    for(int i=0;i<B.size();i++)B[i]=p[i];
    C=A*B;
    // cout<<l<<" "<<r<<' '<<A.size()<<' '<<B.size()<<endl;
    for(int i=mid+1;i-l<C.size()&&i<=r;i++)f[i]+=C[i-(l)];
    solve(mid+1,r);
}
signed main()
{
    cin>>n>>q;n+=2;
    p.resize(n+1);f.resize(n+1);g.resize(n+1);
    f[0]=0,f[1]=1,p[0]=0,p[1]=1,g[0]=0,g[1]=q;
    solve(1,n);
    p[0]+=1;
    Z ans=(p.pow(n,n))[n-1]*Inv(n);
    cout<<ans*power((Z)q,n-1)<<endl;
    return 0;
}

:::

:::info[方法二]

const int mod=998244353;
Z Inv(Z x){return power(x,mod-2);}
int n,q;
Poly p,f,g;
signed main()
{
    cin>>n>>q;n+=2;
    p.resize(n+1);//
    if(q==1)
    {
        p[0]=0;p[1]=1;for(int i=2;i<=n;i++)p[i]=Z(4*i-6)*Inv(i)*p[i-1];
    }
    else if(q==mod-1)
    {
        p[0]=0;p[1]=1;p[2]=mod-1;
        for(int i=3;i<=n;i++)p[i]=((Z)12-4*i)*Inv(i)*p[i-2];
    }
    else 
    {
        f.resize(n+1);g.resize(n+1);f[0]=1;
        for(int i=1;i<=n;i++)f[i]=power((Z)q,2*i-1)*Inv(power((Z)q,i)-1)*f[i-1];
        g[0]=0;for(int i=1;i<=n;i++)g[i]=power((Z)q,i-1)*f[i-1];
        p=g*f.inv(n);p.resize(n);
    }
    p[0]+=1;
    Z ans=(p.pow(n,n))[n-1]*Inv(n);
    cout<<ans*power((Z)q,n-1)<<endl;
    return 0;
}

:::

:::info[方法三]

const int mod=998244353;
Z Inv(Z x){return power(x,mod-2);}
int n,q;
Poly p,f,g;
struct Matrix 
{
    Poly a[2][2];
    Poly*operator[](const int&x){return a[x];}
    Matrix repx(Z q)
    {
        Matrix z(*this);
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        {
            Z v=1;
            for(int k=0;k<a[i][j].size();k++,v*=q)z[i][j][k]*=v;
        }
        return z;
    }
    Matrix operator*(const Matrix&rhs)
    {
        Matrix z;
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)
            z[i][j]=z[i][j]+a[i][k]*rhs.a[k][j];
        return z;
    }
};
signed main()
{
    cin>>n>>q;n+=2;
    p.resize(n+1);
    Matrix M;
    M[0][0]=M[1][0]=Poly({1});M[1][1]=Poly();
    M[0][1]=Poly({0,(Z)mod-1});
    for(int c=1;c<=n+1;c<<=1)M=M.repx(power((Z)q,c))*M;
    Poly A=-M[0][1],B=M[0][0];
    p=A*B.inv(n);p.resize(n);
    p[0]+=1;
    Z ans=(p.pow(n,n))[n-1]*Inv(n);
    cout<<ans*power((Z)q,n-1)<<endl;
    return 0;
}

:::

I

:::info[题面]

给长度为 n 的序列，序列包含 0∼k的整数。称两个长度相同的下标区间是 anagram，若区间里的元素形成的 multiset 相同，把区间的长度称为 anagram 长度。

进行构造：把 0 都改成 1∼k，使得最大 anagram长度最小。

k\le n\le 2\times 10^5

:::

主播现场没过，不要嘲讽主播好喵。

先考虑对于给定的序列，如何求出最大的 anagram 长度。考虑随意构造出一些解，一些显然的情况是，任取两个下标 i<j 且 a_{i}=a_{j}。那么可以取 [i,j-1] 和 [i+1,j] 两个区间，那么这两个区间是 anagram 。证明：

那么，在我们这个 naive 的构造下，最大的 anagram 长度显然是最远的两个相同元素的距离。我们大胆猜想不存在更大的 anagram 长度。下面用反证法证明：

:::info[证明]

设最远的两个相同元素的距离为 k。 假设存在两个区间 [x,y],[p,q]（x<p） 满足他们长度大于 k。那么。

综上，anagram 长度不会超过 k。 :::

经过这么一化简，题目就显得可做多了。由于这显然有单调性，先无脑套个二分上去，问题变为判断是否存在一种构造使得存在每对相同元素的距离都小于等于 x。

对于值 i，我们需要所有值为 i 的元素的距离都小于等于 x，这可以看作我们要用一个长度为 x 的区间覆盖这些元素。

假设在原序列中值为 i 的元素存在于序列中，并且最小下标为 l，最大下标为 r。那么设我们使用的区间放到了 [L,L+x-1]，那么必须保证 [l,r]\in[L,L+x-1]，这就对我们放置的区间提出了一个充要限制。

由于最终序列的位置上每个元素的值都不为 0，这说明所有区间的并集覆盖了所有序列上的点。

那么，这可以看作一个如下的贪心问题。

我们有 k 个长度为 x 的区间，每个区间有一个活动范围，是否存在一种放置方案，能覆盖长度为 m 的区间。

那么从左向右扫描，假设当前扫描到了元素 i，那么维护当前还没有被使用的区间。

代码就不放了，嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤。

L

:::info[题面] 现在有两种类型的树 Tree1 以及 Tree2，且节点数均为 n。

Tree1 满足根节点为 1，其余节点 i 的父亲均为编号比它小的节点 p_i。

Tree2 满足根节点为 n，其余节点i的父亲均为编号比它大的节点 q_i。

现在需要构建一个 Tree1 到 Tree2 的双射，并且满足对于任意节点 i，i 在 Tree1 中为叶子 ⇐⇒ i 在 Tree2 中为非叶子。

:::

:::info[方法 1]

手摸一下小样例：

如果你再手摸一下小样例的话，你会自然而然有这么一个猜想：(从 Tree1 转到 Tree2)

那么，具体化的，我们设 Tree1 中 i 号点及其子树构建的 Tree2 为 Tr_i，根节点为 root_i。我们的想法是自下往上扫描，把构建出来的 Tree2 不断合并。

那么正确性显然：我们构造的方案满足 Tree2 中父亲节点下标大于子节点下标的限制，同时在非叶子节点的合并的时候我们已经确保了所有 \forall i\in[1,k],root_{son_i} 都不是叶子，且 x 一定是叶子，那么也满足了叶子和非叶子的限制。

同时，我们能感觉到，这应该是一个双射：对于两个不同的树（T_x,T_y），从 n\to 1 考虑每个点，若对于点 x，满足 \forall i\in[x+1,n]，T_x 中 i 的儿子和 T_y 中 i 的儿子集合相同；对于点 x 来说，T_x 中和 T_y 中的儿子集合不同。那么显然由于儿子集合不同，合并之后的树的形态也不一样。那么这个应该是对的

那么我们大胆尝试构造从 Tree2 到 Tree1 的逆构造：

可以参考我的实现：

对于每个点 i 维护一个 tag_i 标记，如果 tag_i=1 表示在递归中已经递归到了 i 为根的情况或 i 的子树为根的情况。

那么从 1\to n 扫描每个点，对于点 i，如果 tag_i=1，跳过，否则如果 tag_i=0，说明他还没有成为任何一个递归问题中子树的根，那么让 i 不断往上跳跳到抵押给 tag_{p}=1 的点 p，那么点 i 在递归问题中应该处于以 p 为根的子树内，连边路径上的点并且对路径上的点打标记即可。

由于一个点一旦 tag_i=1 就不会再访问他的父亲，因此复杂度是 O(n) 的

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int r,T,n;
int fa1[N],fa2[N];
vector<int>g[N],q[N];
int dfsA(int x)
{
    vector<int>now;
    for(auto y:g[x])now.push_back(dfsA(y));
    if(now.empty())return x;
    sort(now.begin(),now.end());reverse(now.begin(),now.end());
    for(int i=1;i<now.size();i++)fa2[now[i]]=now[i-1];
    fa2[x]=now.back();
    return now[0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>r>>T;while(T--)
    {
        cin>>n;
        for(int i=0;i<=n;i++)g[i].clear(),fa1[i]=fa2[i]=0;
        for(int i=1;i<=n;i++)cin>>fa1[i],g[fa1[i]].push_back(i);
        if(r==1)dfsA(1);
        else for(int i=1;i<=n;i++)
        {
            //用 fa1[p]=0 表示 tag_p=1
            int p=i,t;while(fa1[p]){t=fa1[p];fa1[p]=0;fa2[p]=i;p=t;}
            if(i!=p)fa2[i]=fa2[p],fa2[p]=i;
        }
        for(int i=1;i<=n;i++)cout<<fa2[i]<<" ";cout<<endl;
    }
    return 0;
}

::::

:::info[方法 2]

（可以看 SUA 官方题解。）

一种截然不同的思路，考虑从 Tree1 递增的构造 Tree2，由于 Tree1 特殊的性质，假设已经构造好了前 n-1 个点，考虑在增加 n 号点的时候原本的构造在 Tree2 中如何变化：（设 i 在 Tree1 中的父亲为 p_i，在 Tree2 中由前 n-1 个点构成的树的父亲为 q_i）

这个操作看起来是双射的，但怎么逆回去看着没有太多思路，再仔细观察，会发现一个神奇的事情：

对于一次操作 a_0=p_n\to a_1...\to a_{m}=n-1\to a_{m+1}=n，假设 Tree2 中前 n-1 个点构成的树中 a_i 的儿子构成的集合除去 a_{i-1} 为 son_{a_i}，那么可以发现 \forall x\in son_{a_i},x<a_i\And x<a_{i+1}，也就是说，在操作完后，a_i 的儿子集合为 a_{i-1} 和 son_{a_{i-1}}，且 a_i 中编号最大的儿子为 a_{i-1}。

也就是说，在 Tree2 中前 n 个点构成的树中，定义重儿子为编号最大的儿子，那么找到以 n 开头的重链就是 n-1 时的操作的 a 序列。

那么我们可以构造出从 Tree2 映射到 Tree1 的操作：

假设当前递归到了 n 号点，找出 n 号点的重链（设为 a_0=p_n\to a_1\to ...\to a_{m+1}=n），那么令 p_n=a_0，然后把 a_i 的儿子移到 a_{i-1} 下面，然后把 n 号点删除，递归操作。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int r,T,n;
int p[N],q[N];
set<int>g[N];
int main()
{
    cin>>r>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>p[i],g[i].clear(),q[i]=0;
        if(r==1)
        {
            for(int i=2;i<=n;i++)
            {
                q[i-1]=i;g[i].insert(i-1);
                int x=p[i];
                vector<int>vt;while(x)vt.push_back(x),x=q[x];
                for(int j=vt.size()-1;j>0;j--)
                {
                    g[vt[j]]=g[vt[j-1]];g[vt[j]].insert(vt[j-1]);
                    if(j-2>=0)g[vt[j]].erase(vt[j-2]);
                    for(auto y:g[vt[j]])q[y]=vt[j];
                }
                g[vt[0]].clear();
            }
        }
        else 
        {
            for(int i=1;i<=n;i++)g[p[i]].insert(i);
            for(int i=n;i>1;i--)
            {
                vector<int>vt;
                int x=i;
                while(x)vt.push_back(x),x=(g[x].empty()?0:*--g[x].end());
                reverse(vt.begin(),vt.end()),q[i]=vt[0];
                for(int j=0;j<vt.size()-1;j++)
                {
                    g[vt[j]]=g[vt[j+1]];g[vt[j]].erase(vt[j]);
                    if(j-1>=0)g[vt[j]].insert(vt[j-1]);
                    for(auto y:g[vt[j]])p[y]=vt[j];
                }
                g[vt.back()].clear();
            }
        }
        for(int i=1;i<=n;i++)cout<<q[i]<<" ";cout<<endl;
    }
}

::::

:::info[方法 3]

主要是 提交记录 #2016963 - QOJ.ac 的思路。

如果你是数学大神的话，你会发现，对于 n 个点的 Tree1 一共有 (n-1)! 种不同的树（对于点 i 来说他的父亲可以取 1 到 i-1 里的任何一个点），而长度为 n 的轮换（只有一个长度为 n 的置换环）恰好有 (n-1)! 种（任取一个起点，对于第 i 个点，作为第 i-1 个点的后继，不能与 1 到 i-1 里面的点相同，即选择方案数为 (n-i)! ）。

也就是说这两者可能存在某种双射，那么我们进行如下构造：

设 P_i 表示 i 的后继，即 (i\to P_i)，设 p_i 表示 i 在 Tree1 中的父亲。

增量构造，现已经构造了前 n-1 个点对应的长度为 n-1 的轮换，考虑加入第 n 个点：

  • 原本是：p_i\to P_{p_i}，插入 i，改为 p_i\to i\to P_{p_i}。

由于显然存在唯一的逆运算，并且构造如下：

设 pre_i 表示存在 pre_i\to i 这条边，即 i 的前驱。

从 n\to 1 递归，对于当前点 i，显然 pre_i 应该是 i 的父亲，那么令 p_{i}=pre_i，并且把边从原来的 P_{pre_i}\to i\to P_i 改为 P_{pre_i}\to P_{i}，同时从 pre_{P_i}=i 改为 pre_{P_i}=pre_i。

那么可以看出来这是一个双射。

另外，我们发现这个构造里面存在一些优美的性质：

由于每次插入时都是形如 p_i\to i\to P_{p_i} 的形式，这说明如果 p_i 为非叶子，那么在 1\to n 的扫描过程中，每次遇到一个 j 满足 p_i 是 j 的父亲，P_{p_i} 就会被更新为 j，而在其他情况下 P_{p_i} 不变。

  • 也就是说，如果 i 为非叶子，那么 P_{i} 恰好就是 i 中的所有儿子编号中最大的一个，即 i<P_{i}

  • 如果 i 为叶子，那么 P_i 只会在插入 i 的时候被更新一次，也就是说 i>P_i

既然 Tree2 要求我们将叶子变为非叶子，将叶子变为非叶子，一个呼之欲出的想法是如果令 i'=n+1-i，那么我们就能更改了不等式的方向，从而改变叶子和非叶子之间的性质。

那么我们创立一个新置换 Q，原本的 i\to P_{i} 在 Q 中变成了 n+1-i\to n+1-P_{i}，即 Q_{n+1-i}=n+1-P_i，那么容易发现以下对应关系：

不过我们想要推出在 Tree2 中的树，由于上面关系中 i 和 n-i+1 并不对应，一个简单的想法是再取一次 n-i+1，即：

对于 Tree1 的一颗树树中的一条边 (i\to p'_i)，构造 Tree2 中的边 n-i+1\to n-p_i+1。

由于之前 i>p'_i，之后有 n-i+1<n-p_{i}+1，也就是说我们的构造合法。也就是说 Tree1 可以不改变树形态的转换到 Tree2。只是每个节点的下标从 i 变成了 n-i+1。

那么，置换 Q 对应的 Tree1，我们把他不改变树形态的转换到 Tree2，有：

  • 在置换 P 对应的 Tree1 中的树中 i 是叶子 \iff 在置换 Q 对应的 Tree1 中的树中 n-i+1 是非叶子 \iff 在置换 Q 对应的 Tree1 中生成的对应 Tree2 的树中 i 是非叶子
  • 在置换 P 对应的 Tree1 中的树中 i 是非叶子 \iff 在置换 Q 对应的 Tree1 中的树中 n-i+1 是叶子 \iff 在置换 Q 对应的 Tree1 中生成的对应 Tree2 的树中 i 是叶子

这样就完成了 Tree1 到 Tree2 的构造。果然很神秘。

另外，对于 Tree2 映射到 Tree1 的情况，我们先将 Tree2 不改变树形态的转化为 Tree1（设其对应的置换为 P），这样子可以推出来：

那么，本题就被神秘的解决了。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int r,T,n;
int p[N],P[N],q[N],pre[N];
void rev(int *a)
//可以看到，置换 P 变换到置换 Q，或者 Tree1 和 Tree2 形态不变的互相转化都是这么写的
{
    reverse(a+1,a+n+1);
    for(int i=1;i<=n;i++)a[i]=!a[i]?0:n-a[i]+1;//根的话强制父亲为 0
}
int main()
{
    cin>>r>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>p[i],P[i]=i;
        if(r==2)rev(p);
        for(int i=2;i<=n;i++)swap(P[p[i]],P[i]);
        rev(P);
        for(int i=1;i<=n;i++)pre[P[i]]=i;
        q[1]=0;for(int i=n;i>=2;i--)q[i]=pre[P[i]]=pre[i],P[pre[i]]=P[i];
        if(r==1)rev(q);
        for(int i=1;i<=n;i++)cout<<q[i]<<' ';cout<<endl;
    }
}

::::