首先可以把操作看成翻转每一段内的数。若总操作次数为奇数则再补充一次即可。
假设数组只包含 $01$，把相邻相同的合在一起，变成形如 $01010101$ 的序列，每次我们翻转第 $2$, $3$ 组，第 $5$, $6$ 组，以此类推。容易发现我们可以在约 $\log_3n$ 次操作中完成排序。
对原数组进行分治即可，注意每层可以同时进行排序。故总操作次数约为 $\frac12\log_3n\log _2n$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #322 for Problem #962. Thanks to MikeMirzayanov
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:04:52
Last updated: 2025-12-14 07:04:55
题解
Comments
No comments yet.