CF round 979 div2(D-E)

lyrrr / 2024-11-06 / 原文

D

容易观察到需要连续一段区间。这不单点修改区间查询，然后我思维就开始往线段树飘了。。。并且我到这里就以为做完了开始想实现，实际上性质都没观察准确。。
但是因为这是一个1500的题所以显然有不用线段树的解。题解是差分做的，确实差分也可以操作区间
观察到“LR”一定是隔断点，那么我们可以维护非法的隔断点数并用cnt统计，这就使维护只影响到相邻位置
最后要考虑的就是如何分区间（到这里又开始混乱），分割区间条件设为当前最大值等于i，也就是说小的数都在前面了不影响后面
然后就做完了
差分的话就是说前面对后面累计影响为0的时候就可以分割区间

#include <bits/stdc++.h>
const int maxn = 2e5+10, mod = 1e9+7;
using namespace std;
#define int long long
#define double long double
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define lowbit(x) (x&(-x))
int n,k,a[maxn],check[maxn];
string s;
int jud(int x){
	if(!check[x]&&s[x]=='L'&&s[x+1]=='R')return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;cin>>t;while(t--){
		int n,q;cin>>n>>q;
		
		for(int i=1;i<=n;i++){
			cin>>a[i];check[i]=0;
		}
		cin>>s;s='1'+s+'R';
		int cnt=0;
		for(int i=1,mx=0;i<=n;i++){
			mx=max(mx,a[i]);
			if(mx==i)check[i]=1;
			cnt+=jud(i);
		}
		while(q--){
			int x;cin>>x;
			cnt-=(jud(x-1)+jud(x));
			s[x]=(s[x]=='L')?'R':'L';
			cnt+= (jud(x-1)+jud(x));
			if(cnt==0)cout<<"yes"<<endl;
			else cout<<"NO"<<endl;
		}
	}
}