B. 三元组

给定排列 $A$, 判断是否存在 $i,j,k$ 满足 $i<j<k$ 且 $2A_j=A_i+A_k$. $n\le 10^5$.

枚举 $j$​, 设 $C$​ 为 $A[1,i]$​ 的计数序列, 发现当前 $j$​ 不合法的条件为 $\forall k,C_k=C_{2j-k}$​, 维护 $C$​ 的正序/逆序哈希判断即可, 使用线段树. 时间复杂度 $O(n\log n)$​.

C. 超命运树

给定长为 $n$ 的排列 $P$. 对于下标集合 $S$, 定义 $A(S)=\{x:\exists l,r\in S,l<r,\min P[l,r]=x\}$, 定义谓词 $B(S)=|S|\le 1\lor (|S|>1\land (\exists x\in S,B(S\setminus\{x\})\land|A(S)|=|A(S\setminus\{x\})|+1))$. 求 $(S,T)$ 的个数, 满足 $T\sub S\sub [1,n]\land B(T)\land |A(S)|=|A(T)|$. $n\le 2\times 10^6$.

D. 刷墙

给定 $n\times m$ 的格子, 格子有颜色, 初始为颜色 $0$, 有若干操作: 将某一区间内的行或列变为某种颜色. 全部操作后, 统计有多少对格子满足有公用边或公用角且二者颜色相同. $n,m,q\le 10^5$.