本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫喝水 普及- T2 午枫的排队 普及- T3 午枫坐公交 普及- T4 午枫的双向奔赴2 普及/提高- T5 午枫的填数游戏 普及/提高- T6 午枫的字符串反转 普及+/提高
T1 午枫喝水
题目大意
分别有两个容量为 aaa 和 bbb 的杯子，经过 kkk 次操作后，求两个杯子中剩余的水的体积。
解题思路
按照题意模拟即可。
参考代码
T2 午枫的排队
题目大意
给定 nnn 个人的回答 aia_iai ，表示第 iii 个人站在第 aia_iai 个人的前面。
解题思路
定义 nxtnxtnxt 数组记录每个人的后一个是谁，单独记录排头，通过循环依次输出所有人的编号。
参考代码
T3 午枫坐公交
题目大意
给定 nnn 次车上人数的变化量，求最后车上可能的最小人数。
解题思路
我们可以先假设上车时车上有 000 人，直接用变化量计算车上的人数总变化量，下车时车上的人数总变化量为 resresres 人，在中间计算过程中，记录下最小的非正数 mimimi ，我们只需要保证在最小的人数时刻为 000 人，那么其他时刻的人数一定大于等于 000 人，故答案为 res+mires+mires+mi 。
参考答案
T4 午枫的双向奔赴2
题目大意
有两个人位于不同的起点，每次移动两人只能往同一方向移动，如果在边界或移动方向有障碍物则不移动，求两人移动到同一点的最短时长。
解题思路
考虑到两个人第一次到达某个位置时，花费的时间最短，不妨设其中一人的位置为 (x1,y1)(x_1,y_1)(x1 ,y1 ) ，另一人的位置为 (x2,y2)(x_2,y_2)(x2 ,y2 ) 。
令 d[x1][y1][x2][y2]d[x_1][y_1][x_2][y_2]d[x1 ][y1 ][x2 ][y2 ] 为一人到达 (x1,y1)(x_1,y_1)(x1 ,y1 ) ，另一人到达 (x2,y2)(x_2,y_2)(x2 ,y2 ) 花费的最短时间。因为每次移动只花费 111 单位时间，所以通过 bfsbfsbfs 即可实现。
时间复杂度 O(n4)O(n^4)O(n4)
参考代码
T5 午枫的填数游戏
题目大意
最初有一个长度 nnn 的序列 aaa 和 qqq 个数对 (pi,vi)(p_i,v_i)(pi ,vi ) ，对于每个数对有两种方式执行操作：
* 将 a1,a2,⋯ ,apia_1,a_2,\cdots,a_{p_i}a1 ,a2 ,⋯,api 替换为 viv_ivi ，次操作前提是 a1,a2,⋯ ,apia_1,a_2,\cdots,a_{p_i}a1 ,a2 ,⋯,api 都小于或等于 viv_ivi 。
* 将 api,api+1,⋯ ,ana_{p_i},a_{p_i+1},\cdots,a_{n}api ,api +1 ,⋯,an 替换为 viv_ivi ，次操作前提是 api,api+1,⋯ ,ana_{p_i},a_{p_i+1},\cdots,a_{n}api ,api +1 ,⋯,an 都小于或等于 viv_ivi 。
问有多少种不同的操作序列，如果不能全部都执行，则输出 0 。
解题思路
首先我们观察到 q≤5000q\leq 5000q≤5000 ，因此可以尝试使用 O(q2)O(q^2)O(q2) 的做法实现。
我们称第 iii 个数对操作为 iii 操作，选择第一种执行方式称为向左操作，选择第二种执行方式成为向右操作。
考虑所有两两数对 (i,j)(i,j)(i,j) 操作之间的关系，有 1≤i<j≤q1\leq i< j\leq q1≤i<j≤q ，有以下几种情况：
* 当 vi≤vjv_i \leq v_jvi ≤vj 时，任意选择即可。
* 当 vi>vjv_i>v_jvi >vj 并且 pi=pjp_i=p_jpi =pj 时，此时这两个操作直接矛盾，答案为 000 。
* 当 vi>vjv_i>v_jvi >vj 并且 pi<pjp_i<p_jpi <pj 时，操作 iii 必须向左操作，操作 jjj 必须向右操作。
* 当 vi>vjv_i>v_jvi >vj 并且 pi>pjp_i>p_jpi >pj 时，操作 iii 必须向右操作，操作 jjj 必须向左操作。
对于第三、四种情况，可能会出现不同数对间接矛盾的情况，此时答案也为 000 。
我们将所有数对操作的可能情况用 −1,0,1-1,0,1−1,0,1 进行表示，其中 −1-1−1 表示向左向右都可，000 表示只能向左，111 表示只能向右。
如果所有操作之间没有矛盾，那么答案至少为 111 ，对于那些上述 −1-1−1 的操作，都有两种选择，其他都只有一种选择，不妨设 −1-1−1 的操作数为 cntcntcnt ，那么答案为 2cnt2^{cnt}2cnt 。注意取模。
参考代码
T6 午枫的字符串反转
题目大意
给定一个长度为 nnn 的 010101 串，有两种查询，第一种查询为反转区间 [L,R][L,R][L,R] 的 0 和 1 ，第二种查询为判断子串 [L,R][L,R][L,R] 是否为好字符串，好字符串的定义为字符串中任意连续的 222 个字符都不相同的字符串是好字符串。
解题思路
不妨设长度为 n−1n-1n−1 的序列 is=(is1,is2,...,isn−1)is=(is_1,is_2,...,is_{n-1})is=(is1 ,is2 ,...,isn−1 ) ，如果 si=si+1s_i=s_{i+1}si =si+1 ，则让 isi=1is_i=1isi =1 ，否则 isi=0is_i=0isi =0 。
对于第一种查询 1 L R ，由于区间 [L,R][L,R][L,R] 内的相邻字符的关系不会发生改变，所以对于整个序列 isisis ，只有 L−1L-1L−1 和 RRR 的位置发生改变，即修改 isL−1is_{L-1}isL−1 为 1−isL−11-is_{L-1}1−isL−1 以及 isRis_{R}isR 为 1−isR1-is_{R}1−isR 。其中，如果 L=1L=1L=1 或 R=nR=nR=n ，则对应序列位置不发生改变。
对于第二种查询 2 L R ，如果 isL=isL+1=⋯=isR−1=1is_L = is_{L+1} = \cdots = is_{R-1} = 1isL =isL+1 =⋯=isR−1 =1 ，那么答案为 Yes ，否则为 No 。
对于以上操作，可以使用线段树或树状数组进行维护和查询。
参考代码
