A
体感难度：红
直接模拟倒水的过程即可，时间复杂度为 O(k)O(k)O(k)。
B
体感难度：橙
队列的第一个元素一定是唯一一个满足 ai≠−1a_i\neq -1ai =−1 的元素，然后维护数组 neine_inei 表示第 iii 个人的后面一个人的编号，显然有 neai=ine_{a_i}=ineai =i。
然后从队首元素 xxx 开始，每一次找到其后面一个元素 nexne_xnex ，然后令 x←nexx\leftarrow ne_xx←nex 即可，总时间复杂度为 O(n)O(n)O(n) 可以通过。
C
体感难度：橙
因为任意时刻车上人数都会 ≥0\ge 0≥0，所以考虑找出一个时刻，使得该时刻人数最少，让这个时刻在车上的人数为 000，维护该时刻和初始时刻（即第一次上下车之前）的相对关系即当前时刻比初始时刻多 / 少了多少个人（这里少用多了负数个人来表示），这是简单的，直接求 aaa 序列的前缀和，找到其前缀最小值 xxx 即可。
最后的答案即为 −x-x−x，时间复杂度为 O(n)O(n)O(n) 可以通过。
D
体感难度：黄
十分的套路，考虑同时维护两个人的位置，设 fx1,y1,x2,y2f_{x_1,y_1,x_2,y_2}fx1 ,y1 ,x2 ,y2 表示当前两个人分别移动到了(x1,y1)(x_1,y_1)(x1 ,y1 ) 和 (x2,y2)(x_2,y_2)(x2 ,y2 ) 两个位置，最少需要从初始状态出发移动多少步，容易发现这个可以直接 BFS 求最短路处理，总状态数为 O(n4)O(n^4)O(n4)，时间复杂度也为 O(n4)O(n^4)O(n4)，可以通过。
E
简要题意：
> 初始有一个长度为 nnn 的序列 aaa，初始有 ai=0a_i=0ai =0。
>
> 现在有 mmm 个数对 (pi,vi)(p_i,v_i)(pi ,vi )，需要按照读入的顺序依次执行这 mmm 个数对，执行方式为在下面两个操作中选择一种：
>
> * 若序列 aaa 满足 maxj=1piaj≤vi\max\limits_{j=1}^{p_i}a_j\le v_ij=1maxpi aj ≤vi ，则可以执行操作 ∀j∈[1,pi],aj←vi\forall j\in[1,p_i],a_j\leftarrow v_i∀j∈[1,pi ],aj ←vi 。
> * 若序列 aaa 满足 maxj=pinaj≤vi\max\limits_{j=p_i}^{n}a_j\le v_ij=pi maxn aj ≤vi ，则可以执行操作 ∀j∈[pi,n],aj←vi\forall j\in[p_i,n],a_j\leftarrow v_i∀j∈[pi ,n],aj ←vi 。
>
> 问有多少种合法的执行方式。
Sol
体感难度：绿~蓝
感觉是这场比赛里唯一有意思的题（）但是被卡了很久
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
看到“从两个操作中选一个操作执行”的字眼，容易想到 2-Sat 模型，因为要求计数方案数，所以容易想到判无解后把所有的操作划分为若干个连通块，然后在每个连通块内计数，在连通块之间直接乘法原理得到答案。
直接做比较困难，考虑先挖掘一下操作的性质。容易注意到 iii 操作会被 jjj 操作所影响，当且仅当 j<ij<ij<i 且 vj>viv_j>v_ivj >vi 。
然后考虑一个位置 iii，设集合 SSS 为所有会影响到 iii 的位置 jjj 组成的集合，那么对这些位置的 pjp_jpj 和 pip_ipi 位置进行分类讨论：
* ∣S∣=0|S|=0∣S∣=0 即不存在会影响到位置 iii 的 jjj，此时该位置不论是覆盖一个前缀还是覆盖一个后缀，都不会导致当前的答案不合法，因此该情况下答案可以乘以 222。
* ∣S∣>0|S|>0∣S∣>0，此时可以 O(n)O(n)O(n) 维护出一个覆盖区间 [l,r][l,r][l,r]，其中 l,rl,rl,r 分别表示所有可以影响到 iii 位置的元素中 pjp_jpj 的最小值和最大值。分类讨论 [l,r][l,r][l,r] 区间和 pip_ipi 的关系：
* 若有 l≤pi≤rl\le p_i\le rl≤pi ≤r，那么此时不论 iii 选择的是覆盖前缀还是覆盖后缀，都会和之前的某次操作产生冲突，此时无合法操作方案，答案为 000。
* 若有 pi<lp_i<lpi <l，则此时 iii 全部覆盖前缀可以不对答案产生影响。
* 若有 pi>rp_i>rpi >r，则此时 iii 全部覆盖后缀可以不对答案产生影响。
直接按照上述的方法计数会产生后效性，即可能在某一次操作中满足 ∣S∣=0|S|=0∣S∣=0，前缀和后缀都可以选，但是在之后的某次操作中因为后面的这个操作和前面的操作产生了冲突，导致两次操作选择的是前缀还是后缀都固定了。因此容易想到解决方案：
* 提前对每个位置 iii 处理出其会被影响到的区间 [li,ri][l_i,r_i][li ,ri ]。
* 只考虑所有 ∣Si∣=0|S_i|=0∣Si ∣=0 即自己不会被任何区间影响的区间，然后枚举 j=i+1…nj=i+1\ldots nj=i+1…n，若 jjj 所对应的操作会被 iii 所对应的操作影响，则 iii 操作就不能自由选择操作的是前缀还是后缀。
* 若不存在 jjj 会被 iii 影响，则 iii 可以自由选择操作前缀还是后缀，答案可以乘以 222。
最后判断无解的情况：
* 在前文考虑对于位置 iii，判断是否有位置 jjj 会被位置 iii 影响的时候，考虑记录是否存在两个操作使得 iii 分别不能选择前缀 / 后缀，若存在这样的两个操作，那么显然无解，输出 000 即可。
* 对于位置 iii，若有 li≤pi≤ril_i\le p_i\le r_ili ≤pi ≤ri ，那么此时不论 iii 选择的是覆盖前缀还是覆盖后缀，都会和之前的某次操作产生冲突，此时无合法操作方案，答案为 000。
直接模拟上述过程，时间复杂度为 O(n2)O(n^2)O(n2) 可以通过，容易发现上述过程可以用线段树等 ds 优化到 O(nlogn)O(n\log n)O(nlogn)。个人感觉不太能做到严格线性，如果有做法的话可以在评论区留言（）
F
这不纯唐题（）考虑维护两个线段树，维护的信息分别为：
* 字符串 sss 中第 iii 个位置的值
* 区间 [l,r][l,r][l,r] 中 ∑i=lr[si=si+1]\sum\limits_{i=l}^r[s_i=s_{i+1}]i=l∑r [si =si+1 ] 的值
判断一段区间 [l,r][l,r][l,r] 合法可以查询在第二棵线段树中查询区间 [l,r−1][l,r-1][l,r−1] 的值，若其值为 000 则该区间组成的字符串合法，否则不合法。
而对于区间 [l,r][l,r][l,r] 的修改操作，在维护字符串值的线段树中可以直接打懒标记维护，而在维护区间内相邻元素相同的位置的数量的线段树中，注意到只有边界上下标为 l−1,l,r−1,rl-1,l,r-1,rl−1,l,r−1,r 的位置的值会变化，所以对这四个位置做单点修改即可。
总时间复杂度为 O(nlogn)O(n\log n)O(nlogn)，可以通过。
