观察：如果我们规定 $A_i=A_{i+1}$ 的时候不能交换，则每个不同序列对应唯一的操作方式。
现在相当于将原序列分成若干段，每一段的开头不断交换至结尾，因此要求段的开头只能出现一次。从后往前 DP，找到第 $i$ 个数右边第一个相同数的位置 $f_i$，则可以从 $[i+1,f_i]$ 转移到 $i$，用前缀和优化即可。时间复杂度 $O(N)$。
QOJ.ac
QOJ
The 3rd Universal Cup Finals is coming! Join our Warm-up Game and Prediction Game and win the prizes! Learn more...
Discussion #1409 for Problem #17250. Exchange or Not
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-04-05 16:29:36
Last updated: 2026-04-05 16:29:40
题解
Comments
No comments yet.