AGC001

AtCoder Grand Contest 001

Problem E

由于每个\((i, j)\)对答案的贡献是\(a_i+b_i+a_j+b_j\choose a_i\),立即考虑单调路径模型。

发现贡献可以看作\((-a_i, -b_i) \rightarrow(a_j, b_j)\)。

由于值域只有\(2e4\), 直接对所有从第三象限到第一象限的路径DP即可。

F - Wide Swap

通过计算pos数组，操作被转化为\(swap(pos_i, pos_{i+1})\)仅当\(|pos_i-pos_{i+1}|\ge K\)， 要求\(1,2,\ldots,n\)贪心地在pos最前。

显然，\(|pos_i-pos_j|\lt K\)的\((i, j)\)顺序不变。对所有这样的\((i,j)\)从i向j连边，形成DAG。

答案即是字典序最小的拓扑排序。

考虑贪心地对没有出边的最大的点赋予更大的序号，这样的\(i\)满足\(P_i=\underset{i-K+1\le j\le i+K-1} {\operatorname{argmax}} P_j\)。

priority_queue + 线段树RMQ。\(O(n\log n)\)