【前缀和】【分类讨论】【二分查找】2983：回文串重新排列查询

class Solution {
public:
  vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
    const int n2 = s.length() / 2;
    vector<vector<int>> vPreSumLeft(26, vector<int>(1)), vPreSumRight(26, vector<int>(1));
    vector<int> vNotSame;
    for (int i = 0; i < n2; i++)
    {
      for (int j = 0; j < 26; j++)
      {
        vPreSumLeft[j].emplace_back(vPreSumLeft[j].back() + (j + 'a' == s[i]));
        vPreSumRight[j].emplace_back(vPreSumRight[j].back() + (j + 'a' == s[s.length() - 1 - i]));
      }
      if (s[i] != s[s.length() - 1 - i])
      {
        vNotSame.emplace_back(i);
      }
    }
    auto IsSame = [&](int a, int b)
    {
      for (int i = 0; i < 26; i++)
      {
        if (vPreSumLeft[i][b + 1] - vPreSumLeft[i][a] != vPreSumRight[i][b + 1] - vPreSumRight[i][a])
        {
          return false;
        }
      }
      return true;
    };
    auto NotSameCount = [&](int a, int b)
    {
      return std::upper_bound(vNotSame.begin(), vNotSame.end(), b) - std::lower_bound(vNotSame.begin(), vNotSame.end(), a);
    };    
    vector<bool> vRet;
    for (const auto& v : queries)
    {
      const int a = v[0], b = v[1], c = s.length() - 1 - v[3], d = s.length() - 1 - v[2];
      const int iCrossLeft = max(a, c), iCrossRight = min(b, d);
      const int iCrossLen = iCrossRight - iCrossLeft + 1;
      auto Has = [&](const int a, const int b,const vector<int>& vPreSum, const vector<int>& vPreSumOther)
      {//[a,b]可以任意调整顺序的范围，[c,d]是非交叉范围
        int c = a, d = iCrossLeft-1;
        if (a == iCrossLeft)
        {
          c = iCrossRight+1;
          d = b;
        }
        return (vPreSum[b + 1] - vPreSum[a] - (vPreSumOther[d + 1] - vPreSumOther[c])) >= 0;
      };
      if (iCrossLen <= 0)
      {//两者没有交叉
        const int iNotSameCount = NotSameCount(a, b) + NotSameCount(c, d);
        vRet.emplace_back(IsSame(a, b) && IsSame(c, d) && (iNotSameCount == vNotSame.size()));
      }
      else
      {
        const int iUnion1 = min(a, c),  iUnion2 = max(b, d);
        auto IsInclude =[&](const int a, const int b)
        {
          return (iUnion1 == a) && (iUnion2 == b);
        };
        if (IsInclude(a, b) || IsInclude(c, d))
        {
          vRet.emplace_back(IsSame(iUnion1, iUnion2) && (NotSameCount(iUnion1, iUnion2) == vNotSame.size() ));
          continue;
        }
        bool bHas = true;
        for (int i = 0; i < 26; i++)
        {
          bHas &= Has(a,b, vPreSumLeft[i], vPreSumRight[i]);
          bHas &= Has(c, d, vPreSumRight[i], vPreSumLeft[i]);
        }
        vRet.emplace_back(bHas&& IsSame(iUnion1, iUnion2) && (NotSameCount(iUnion1, iUnion2) == vNotSame.size()));
      }
    }
    return vRet;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string s, p;
  vector<vector<int>>queries;
  {
    Solution sln;
    s = "fxdqcfqdxc", queries = { {1,1,7,8},{1,1,5,9},{2,4,8,8},{0,4,6,8},{2,3,7,8},{2,4,5,9},{1,4,9,9} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{false, true, false, true, false, true, false}, res);
  }
  {
    Solution sln;
    s = "dbaabd", queries = { {0, 1, 5, 5}, { 1,2,4,5 } };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{true,true}, res);
  }
  {
    Solution sln;
    s = "ceddceddcc", queries = { {0,1,6,8} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{false}, res);
  }
  {
    Solution sln;
    s = "acbcab", queries = { {1,2,4,5} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{true}, res);
  }
  {
    Solution sln;
    s = "abbcdecbba", queries = { {0,2,7,9} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{false}, res);
  }
  {
    Solution sln;
    s = "abcabc", queries = { {1,1,3,5},{0,2,5,5} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{true, true}, res);
  }
  {
    Solution sln;
    s = "odaxusaweuasuoeudxwa", queries = { {0,5,10,14} };
    auto res = sln.canMakePalindromeQueries(s, queries);
    Assert(vector<bool>{false}, res);
  }
}