CF2030D QED's Favorite Permutation 题解

CodeFancy 好喜欢考察这个 Trick 啊，已经见到第三次了。

首先手玩可以发现，不能交换两个位置 $i,j$ 上的数当且仅当 $x \in [i,j),s_x = L,s_{x+1} = R$。转换一下视角，由于是看全局能不能排序，所以我们可以预处理哪些位置 $x$ 满足 $s_x=L,s_{x+1}=R$ 的条件会使得答案为否。这个可以直接对于每一个 $[\min(a_i,i),\max(a_i,i))$ 差分去打一个区间加标记来解决。

然后对于每一次单点修改你就更新一下 $x,x-1$ 这两个位置对答案的贡献就行了。复杂度是 $O(n)$。

// Problem: D. QED's Favorite Permutation
// URL: https://codeforces.com/contest/2030/problem/D
// Writer:WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 5e5 + 10;

int a[MAX];
int s2[MAX];

void solve(){
   int n = read(), m = read();
   for(int i = 1; i <= n; i++){
   	a[i] = read();
   }
   string s;
   cin >> s;
   int l = 1, r = 0;
   for(int i = 1; i <= n; i++){
   	s2[i] = 0;
   }
   for(int i = 1; i <= n; i++){
   	int L = min(a[i], i), R = max(a[i], i);
   	s2[L]++;
   	s2[R]--;
   }
   int now = 0;
   for(int i = 1; i <= n; i++){
   	now += s2[i];
   	s2[i] = now;
   }
   // while(a[l] == l and l <= n){
   	// l++;
   // }
   // while(a[r] == r and r >= 1){
   	// r--;
   // }
   // // write(l), endl;
   // if(l == n + 1){
   	// while(m--){
   		// int x = read();
   		// puts("YES");
   	// }
   	// return ;
   // }
   int cnt = 0;
   for(int i = 1; i < n; i++){
   	if(s2[i] and s[i - 1] == 'L' and s[i] == 'R'){
   		cnt++;
   	}
   }
   while(m--){
   	int x = read();
   	// if(x < l or x > r){
   		// if(cnt)	puts("NO");
   		// else puts("YES");
   		// continue;
   	// }
   	int pre = 0;
   	if(s2[x - 1])	pre += (s[x - 2] == 'L' and s[x - 1] == 'R');
   	if(s2[x])	pre += (s[x - 1] == 'L' and s[x] == 'R');
   	int now = 0;
   	if(s[x - 1] == 'L')	s[x - 1] = 'R';
   	else s[x - 1] = 'L';
   	if(s2[x - 1])	now += (s[x - 2] == 'L' and s[x - 1] == 'R');
   	if(s2[x])	now += (s[x - 1] == 'L' and s[x] == 'R');
   	cnt += now - pre;
   	// write(cnt), put(), write(pre), endl;
   	if(cnt){
   		puts("NO");
   	}else{
   		puts("YES");
   	}
   }
}

signed main(){
   int t = read();
   while(t--)	solve();
   return 0;
}