赛时写的，所以是今晚。
谁懂 18min 切 ABC 1h 切 D1 然后 1h 坐牢无果放弃的救赎感。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A
题意解析：给定一个 nnn 的排列 AAA。你需要将它染色，使它满足：
* 对于所有 1≤i<n1\le i\lt n1≤i<n，AiA_iAi 颜色与 Ai+1A_{i+1}Ai+1 颜色不同。
* 将 AAA 从小到大排序，每个数颜色不变，然后依然满足对于所有 1≤i<n1\le i\lt n1≤i<n，AiA_iAi 颜色与 Ai+1A_{i+1}Ai+1 颜色不同。
你需要判断是否存在一种合理的染色方法是上面两个条件成立。
注意到染色方法只有一种。所以暴力判断即可。
时间复杂度：O(tnlogn)O(tn\log n)O(tnlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B
题意解析：给定一个长度为 nnn 的数组 AAA。你需要重排 AAA，使它满足：
* 对于所有 1≤i<n1\le i\lt n1≤i<n，[1,i][1,i][1,i] 的 mex\text{mex}mex 与 [i+1,n][i+1,n][i+1,n] 的 mex\text{mex}mex 不同。
请你判断是否存在。
显然有个贪心做法：将所有的 000 都放在后面，其他放在前面。
分类讨论一下会发现满足 min(mex([A1,...,Ai]),mex([Ai+1,...,An]))≤1\min(\text{mex}([A_1,...,A_i]),\text{mex}([A_{i+1},...,A_n]))\le 1min(mex([A1 ,...,Ai ]),mex([Ai+1 ,...,An ]))≤1。
* 如果两个的 mex\text{mex}mex 都为 000 的话，则 AAA 中没有 000，显然无论如何重排都不行。
* 如果两个的 mex\text{mex}mex 都为 111 的话，则 AAA 至少有两个 000 且没有 111，此时将 AAA 任意重排：
定义数组 BBB，满足 Bi=[Ai=0]B_i=[A_i=0]Bi =[Ai =0]。显然如果 max[Bl,...,Br]=1\max[B_l,...,B_r]=1max[Bl ,...,Br ]=1，则 mex[Al,...,Ar]=1\text{mex}[A_l,...,A_r]=1mex[Al ,...,Ar ]=1，否则 mex[Al,...,Ar]=0\text{mex}[A_l,...,A_r]=0mex[Al ,...,Ar ]=0。
显然无论如何重排，都存在 max([B1,...,Bi])=max([Bi+1,...,Bn])=1\max([B_1,...,B_i])=\max([B_{i+1},...,B_n])=1max([B1 ,...,Bi ])=max([Bi+1 ,...,Bn ])=1。
所以这个贪心是正确的。
时间复杂度：O(tnlogn)O(tn\log n)O(tnlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C
题意解析：Alice 和 Bob 在玩一个游戏。给定一个 010101 串 AAA。他们会轮流对 AAA 进行操作：
* 选定几个数 p1,p2,p3,...p_1,p_2,p_3,...p1 ,p2 ,p3 ,...，使得对于任意 i<ji\lt ji<j，Api≥ApjA_{p_i}\ge A_{p_j}Api ≥Apj 。
* 通过对 Ap1,...A_{p_1},...Ap1 ,... 交换使得对于任意 i<ji\lt ji<j，Api≤ApjA_{p_i}\le A_{p_j}Api ≤Apj 。
谁先让 AAA 升序谁就赢了。
问谁会获胜，若 Alice 获胜输出先手操作。
我们可以画图模拟。
会发现有若干个“峰”（两边为 000 中间为 111 的块）和若干个“谷”（两边为 111 中间为 000 的块）。我们只需要把这几个“峰”和“谷”消掉就行了。
模拟一下，发现把前面的“峰”和后面的“谷”选了就能一次性全消掉了。
双指针解决。
时间复杂度：O(∑nlogn)O(\sum n\log n)O(∑nlogn)。
D1
时间主要花在对拍上了。
题意解析：定义一个括号串 SSS“优于”另一个括号串 TTT 如下：
* TTT 是 SSS 的前缀且 S≠TS\not= TS=T，或
* 存在一个整数 iii 满足对于所有 1≤j<i1\le j\lt i1≤j<i 满足 Sj=TjS_j=T_jSj =Tj ，且 Si=(,Ti=)S_i=(,T_i=)Si =(,Ti =)。
给定一个匹配的括号串 AAA，请你求出所有优于 AAA 且为 AAA 的子匹配括号串中，长度最大值。
考虑贪心。
显然第一个条件没用。
我们可以枚举 iii 在哪里，使保证：
* iii 前面的全选。
* AiA_iAi 为 )))，然后答案选一个 (((。
* 后面的在能与前面的匹配的情况下，能选多少选多少。
显然后面的所有 ))) 尽量与前面多的 ((( 匹配；如果还有多的，那就可以和后面的 ((( 匹配。
所以我们只需要处理出：
* iii 后面的 ((( 和 ))) 个数。
* iii 后面第一个 ((( 的下标。
然后就解决了。
时间复杂度：O(∑n)O(\sum n)O(∑n)。
