根据数据可知,字符串s被分成互不相交的子集,然后在每个子集内根据x的位置经行左右翻转,可知翻转为偶数时恢复原样,所以可以根据差分数组进行求解
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int a[N], b[N];
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
for (int i = 1; i <= k; i++) cin >> a[i];
for (int i = 1; i <= k; i++) cin >> b[i];
int q;
int cnt[N] = {};
cin >> q;
while (q--) {
int x;
cin >> x;
int p = lower_bound(b + 1, b + 1 + k, x) - b;//寻找x的下标,x<=b[i]
int a1 = min(x, b[p] + a[p] - x), b1 = max(x, b[p] + a[p] - x);
cnt[a1] ++; cnt[b1 + 1]--;//差分
}
string ans = s;
int now = 0;
for (int i = 1; i <= k; i++) {
for (int j = a[i]; j <= b[i]; j++){
now += cnt[j];//前缀和
if (now & 1) {//是奇数就翻转
ans[j-1] = s[a[i]+b[i] - j-1];
}
}
}
cout << ans;
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}