Readme

2983.Palindrome-Rearrangement-Queries

首先我们预处理一下，将s的后半段翻转之后记为t，令s和t的长度都是m=n/2。并且将两个字符串都看做1-index。

我们容易得到s中可以重排的区间记做[a,b]，t中可以重排的区间记做[c,d]. 考虑到这两个区间可能有多种交汇的可能：不相交、相交但不包含，完全包含。我们做如下区间处理：

1. 计算相交的区间，记做cross：{max(a,c), min(b,d)}，注意该区间可能为空。
2. 计算属于区间ab但不属于cd的区域，记做A
   cppCopy

   if (a<=c-1) A.push_back({a, c-1});
   if (d+1<=b) A.push_back({d+1, b});
   

3. 计算属于区间cd但不属于ab的区域，记做B
   cppCopy

   if (c<=a-1) B.push_back({c,a-1});
   if (b+1<=d) B.push_back({b+1,d});
   

4. 计算要么属于ab要么属于cd的区间，记做Union，其实就是以上cross, A, B里面区间的合并。

判断合法的条件有如下：

1. 在Union之外的区域，必须要求s和t每个字符都相等。这里有一个巧妙的判定方法。我们构造前缀数组diff[i]表示前i个位置里有多少个s与t字母不相同的位置。于是我们只需要查验Union里面的、不同字母的位置个数，是否等于diff[m]即可。
2. 对于A区间，s里面的字符调整后必须和t里面的字符完全一致。所以我们先将s在区间ab的字符频次放入count1，再消耗掉t在区间A里的字符频次。要求不能出现负数。
3. 对于B区间，t里面的字符调整后必须和s里面的字符完全一致。所以我们先将t在区间cd的字符频次放入count2，再消耗掉s在区间B里的字符频次。要求不能出现负数。
4. 最后，剩余的count1和count2代表了cross部分，两者的字母频次必须完全一致。