有这样一个结论，由 \(x\) 得到的反转区间 \([a,b]\) 的对称轴就是 \(x\) 所在的题给区间 \([l,r]\) 的对称轴，且 \([a,b]\subset [l,r]\)。
这个结论有什么用？如果没有这个结论，我们离线 \(q\) 次询问得到的是一系列散乱的反转区间。因为反转区间可能有覆盖、重叠，要得到答案只能暴力地 \(O(qn)\) 去反转 \(s\)，没法整合在一起来降低复杂度。但是一旦有了这个结论，我们就知道：反转区间要么不重叠，要么关于同一个轴对称，我们可以把同轴对称（\(x\) 属于同一个区间）的反转区间整合在一起。
如何整合？朴素的想法是把每个反转区间在原序列上标记 +1。如果一个位置被奇数个反转区间覆盖，则与其对称位置交换；否则不交换。因为只有一次查询，所以可用差分+前缀和优化。
赛时找到了一个错误的结论：每个反转区间长度都小于 \(x\) 所在区间 \([l,r]\) 的长度，所以 \(q\) 次询问加起来的总长度似乎是 \(n\) 量级的。但是，\(q\) 次询问的 \(x\) 可以重复，它完全有可能就着最长的区间反复选择，或者直接选 \(q\) 次 \([1,n]\)！
下面是 AC 代码：
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> l(k + 1), r(k + 1), c(n + 1), p(n + 2);
// c记录x所属区间，p为差分数组
for (int i = 1; i <= k; i++) {
cin >> l[i];
}
for (int i = 1; i <= k; i++) {
cin >> r[i];
for (int j = l[i]; j <= r[i]; j++) {
c[j] = i;
}
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int a = min(x, r[c[x]] + l[c[x]] - x);
int b = max(x, r[c[x]] + l[c[x]] - x);
p[a]++, p[b + 1]--;
}
for (int i = 1; i <= n; i++) {
p[i] += p[i - 1];
}
for (int i = 1; i <= k; i++) {
for (int j = l[i]; j <= (l[i] + r[i]) / 2; j++) {
if (p[j] & 1) {
swap(s[j - 1], s[r[i] + l[i] - j - 1]); // 如果被奇数个区间覆盖，即交换（注意string下标-1）
}
}
}
cout << s << endl;
}