CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
内容提要
本文讨论了数组排序、字符串翻转、数组匹配和子串求和等编程题目，提供了基本思路和解决方案，涉及插入排序、翻转操作和数组排列等算法，旨在帮助读者理解和解决编程挑战。
延伸解读
从插入排序视角理解A题
A题要求判断能否通过特定交换操作将数组排序。文章指出，只需检查第一个元素是否为1即可。这源于插入排序的思想：如果第一个元素是1，那么后续元素可以通过操作逐步归位；否则无法完成排序。这种简化判断避免了模拟整个排序过程，体现了对问题本质的洞察。
B题中连续AB对的翻转策略
B题要求最大化翻转AB子串的次数，且每个下标只能翻转一次。文章分析，对于连续的AAAABBB结构，除最后一个位置外，其他位置都能参与翻转。对于多组连续段，整体上除最后一个位置外也都能翻转。因此，算法通过从右向左统计B的数量和标志位来计算最大翻转次数，最后减一得到答案。
C题匹配数组的构造方法
C题给定两个数组A和B，允许重排B，要求恰好有x个位置满足a_i > b_i。文章提出一种简单构造：将A和B分别排序，然后将B的前x个元素循环右移x位，再检查满足条件的数量是否为x。若满足则输出重排后的B，否则输出NO。这种方法利用了排序后的单调性，通过调整位置来精确控制满足条件的数量。
D题子串求和与奇偶性处理
D题数组仅由1和2组成，支持修改和查询是否存在子串和为x。文章指出，由于元素为1或2，总和s的子串和可以取到s, s-2, s-4,...直到0或1。因此，若x与s奇偶性相同且x≤s，则直接回答YES；若奇偶性不同，则需要减去一个1，即找到左右两边最近的1，计算减去该1及其一侧所有2后的最大可能和，再判断x是否不超过该值。
Q&A
如何通过插入排序判断数组是否可以排序？
只需确保数组的第一个值是正确的，即可判断整个数组是否可以排序。
翻转由'A'和'B'组成的字符串的关键是什么？
关键在于找到连续的'AB'对，以最大化翻转次数。
如何判断两个数组是否可以匹配特定条件？
通过排序两个数组，并调整B数组的前x个值来满足条件。
如何判断由1和2组成的数组中是否存在特定和的子串？
只需维护数组的总和，并根据总和判断是否可以得到特定和。
排列数组的排序过程如何优化？
使用线段树来优化移动成本，确保每个值最终到达正确位置。
在数组中如何处理翻转操作的次数？
需要找出连续的'AB'对的数量，以计算最多可以翻转多少次。
