Codeforces Round 997 (Div. 2) 题解（A~D 题）
A
因为 \(x,y < m\)，所以每次必有重叠的长方形。
且重叠部分长为 \(m-x\)，宽为 \(m-y\) ，用总周长减去算重了的部分就行。
注意处理第一个长方形的边界条件。
B. Find the Permutation
按照 \(g_{i,j}\) 的大小关系直接写 cmp 然后 sort 就行。
考场还写了拓扑（
C. Palindromic Subsequences
构造：\(1,1,2,3,\cdots,n-3,1,2\)。
\(g(a) = n-3 + n-4 + n-4 = 3n-11 > n\)
即 \(n > 5.5\) 都可满足。
D
场切 *2200 ?!
感觉好数组不是很好统计啊，正难则反，我们统计坏数组的数量。
看到值域很小，考虑从值域下手。
坏数组形如：
\[\cdots,x,y,\cdots \]其中 \(y > x\), \(x\) 为第 \(\frac{len}{2}\) 个数。
我们枚举这个 \(x\)，统计所有第 \(\frac{len}{2}\) 个数为 \(x\) 的坏数组数量。
我们将 \(a_i \ge x\) 的数打成 \(1\)，\(a_i < x\) 的数打成 \(0\)，然后做个前缀和。
问题似乎转化为：
统计多少 \(1 \le l \le r \le n\)
\[sum_r -sum_{l-1} = \frac{r-l+1}{2} \]通过一个常用的 trick 可以化成：
\[2sum_r - sum_{l-1} = r-l+1 \]\[(2sum_r-r) - (sum_{l-1}-l+1) = 0 \]令 \(S_i = 2 \times sum_i - i\)，就可以化成：
\[S_r - S_{l-1} = 0 \]这个就可以轻松地用 map 计数了。
但是还没完。
我们发现这个算法有点问题。
比如：
\(1 \ 10\)
在 \(x=1\) 的时候会统计一遍，而在 \(x = 2\) 时，会再次统计一遍。
我们加入一条限制：\([l,r]\) 中必须包含 \(x\)，加上 \(S_r - S_{l-1}=0\) 的条件，便能实现不重不漏。
我们从头到尾枚举 \(r\)，当遇到一个 \(x\) ，就把 \(x\) 前面的 \(S_l\) 加进 map 内，保证 map 内取到的 \(S_i\) 都能保证 \([l,r]\) 内有 \(x\)。
本题就做完了。
标签：997,le,题解,sum,Codeforces,cdots,Div From： https://www.cnblogs.com/codwarm/p/18678087