Solution
A
若二元组 ( i , j ) (i,j) (i,j) 合法，当且仅当 S i < S j S_i < S_j Si<Sj 。
我们从后往前枚举 i i i ，并通过一个桶来找到最靠后的满足 S i < S j S_i<S_j Si<Sj 的 j j j；若存在一个这样的 j j j，则直接输出即可。
时间复杂度 O ( n ) O(n) O(n) 。
B
我们找到黑色棋子的气，然后对于气的每一个连通块判断它的气是否为 0 0 0 即可。若气为 0 0 0 的气不超过 1 1 1 个，则答案为 NO \text{NO} NO，否则为 YES \text{YES} YES。
C
不会 ⋯ ⋯ \cdots\cdots ⋯⋯
D
考虑分治。
令当前分治区间为 [ l , r ] [l,r] [l,r]，中间点为 m i d mid mid，我们需要求出所有跨越中间点的区间的最大独立集之和。
令 f i , 0 f_{i,0} fi,0 表示，若 a m i d a_{mid} amid 不在独立集中，区间 [ i , m i d ] [i,mid] [i,mid] 的最大独立集。 f i , 1 f_{i,1} fi,1 则为 a m i d a_{mid} amid 无限制的情况下的最大独立集。
令 g i , 0 g_{i,0} gi,0 表示，若 a m i d + 1 a_{mid+1} amid+1 不在独立集中，区间 [ m i d + 1 , i ] [mid+1,i] [mid+1,i] 的最大独立集。 g i , 1 g_{i,1} gi,1 同理。
若 l ≤ a ≤ m i d < b ≤ R l \le a \le mid < b \le R l≤a≤mid<b≤R，则 f ( a , b ) = max ( f a , 0 + g b , 1 , f a , 1 + g b , 0 ) f(a,b)=\max(f_{a,0}+g_{b,1},f_{a,1}+g_{b,0}) f(a,b)=max(fa,0+gb,1,fa,1+gb,0) 。现在，关键在于求出
∑ a = l m i d ∑ a = m i d + 1 r max ( f a , 0 + g b , 1 , f a , 1 + g b , 0 ) \sum_{a=l}^{mid} \sum_{a=mid+1}^r \max(f_{a,0}+g_{b,1},f_{a,1}+g_{b,0}) a=l∑mida=mid+1∑rmax(fa,0+gb,1,fa,1+gb,0)
我们枚举 a a a，并计算其贡献。直接计算较为困难，于是考虑将 max \max max 去掉。
若 f a , 0 + g b , 1 > f a , 1 + g b , 0 f_{a,0}+g_{b,1} > f_{a,1}+g_{b,0} fa,0+gb,1>fa,1+gb,0，则显然是 f a , 0 + g b , 1 f_{a,0}+g_{b,1} fa,0+gb,1 产生贡献。考虑怎样的 b b b 才能满足上述式子，不难得到
f a , 0 − f a , 1 > g b , 0 − g b , 1 f_{a,0}-f_{a,1} > g_{b,0}-g_{b,1} fa,0−fa,1>gb,0−gb,1
也就是说，我们要求出所有满足 g b , 0 − g b , 1 < f a , 0 , f a , 1 g_{b,0}-g_{b,1} < f_{a,0},f_{a,1} gb,0−gb,1<fa,0,fa,1 的 g b , 1 g_{b,1} gb,1 的数量与 g b , 1 g_{b,1} gb,1 的和。我们可以将它“离线”下来，通过排序与双指针来求出这两个值。
f a , 1 + g b , 0 f_{a,1}+g_{b,0} fa,1+gb,0 产生贡献的情况同理。
令时间复杂度为 T ( n ) T(n) T(n)，则 T ( n ) = 2 T ( n 2 ) + n log n = O ( n log 2 n ) T(n)=2T(\frac n 2)+n \log n=O(n \log^2 n) T(n)=2T(2n)+nlogn=O(nlog2n)。
E
Lemma
F ( i , j ) = 2 F ( i + 1 , j − 1 ) + F ( i , j − 1 ) − F ( i + 1 , j ) F(i,j)=2F(i+1,j-1)+F(i,j-1)-F(i+1,j) F(i,j)=2F(i+1,j−1)+F(i,j−1)−F(i+1,j)
观察上面的式子，不难发现：我们只需要求出第 1 1 1 列的所有 F F F 与第 m m m 列的所有 F F F ，然后直接递推就好了。
时间复杂度 O ( m 2 ) O(m^2) O(m2)。