题目传送门
题目描述
给定一个长度为 \(n\) 的排列 \(p\)（包含从 \(1\) 到 \(n\) 的所有数字），对应一串只由 L 和 R 组成的字符串，L 表示这个数可以和左边相邻的数字交换，R 表示这个数可以和右边相邻的数交换。\(q\) 次询问每次改掉字符串中的一个字符（L 改为 R，R 改为 L），且每次修改后保留，问每次修改后是否能通过字符串中的 L 和 R 操作将此排列非降序排序。
解题思路
通过题意，我们会发现，一个数字 \(p_i\) 可以向右交换，当且仅当 \(s_i=\)R 或者 \(s_{i+1}=\)L。换句话说，对于一个 \(i(1\le i\le n)\)，只要 \(s_i=\)L 并且 \(s_{i+1}=\)R，\(p_i\) 及其左边的数就永远交换不到右边，\(p_{i+1}\) 及其右边的数也永远交换不到左边，我们暂称 \(i\) 和 \(i+1\) 这条“无法逾越的线”叫做分界线。那么只要在这条分界线左边（从 \(p_1\) 到 \(p_i\)）没有涵盖从 \(1\) 到 \(i\) 所有的数，那么它所缺少的数在分界线右边，永远不会交换到 \(1\) 到 \(i\) 内，此时序列永远不会非降序排序。只要序列中存在这样的分界线，答案一定是 NO，我们称这种分界线为对答案有贡献的分界线。
所以我们只需要维护这种对答案有贡献的分界线的个数 cnt，cnt 非零就输出 NO，否则就是 YES。这样一来，预处理是必不可少的，定义 bool 类型 check 数组，其中 \(check_i\) 表示从 \(p_1\) 到 \(p_i\) 是否涵盖了从 \(1\) 到 \(i\) 的所有数字，并定义一个 set 来存储所有的分界线的左下标。
对于每次修改 \(s_i\)，如果 \(i\) 或者 \(i-1\) 为分界线的下标，说明这次修改把分界线破坏掉了，将其在 set 中删除，再根据分界线的下标确定是否将对答案有贡献的分界线破坏掉了，如果是，更新 cnt。修改完后，判断此时 \(s_i\) 与其左边或者右边是否又组成了新的分界线，将分界线存入 set 中，并判断根据分界线左下标的 check 判断此分界线是否为对答案有贡献的分界线，更新 cnt。然后根据当前 cnt 值输出就可以了。
AC Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<set>
#define N 200005
using namespace std;
int T,n,q;
int a[N];//序列p
char s[N];
bool check[N];
set<int>st;
int re()//防止作弊不放快读快写
void wr(int x)
signed main()
{T=re();while(T--){int maxx=0,cnt=0;//maxx代表当前所输进来的最大值n=re(),q=re();for(int i=1;i<=n;i++)a[i]=re(),maxx=max(maxx,a[i]),check[i]=(maxx==i);//如果maxx不是i，说明当前p1~pi中有比i大的数，则p1~pi肯定不会涵盖1~i的所有元素cin>>s;for(int i=n;i;i--)s[i]=s[i-1];s[0]=0;//手动将字符串改为下标为1~n的for(int i=1;i<n;i++)if(s[i]=='L'&&s[i+1]=='R')//分界线{st.insert(i);if(!check[i])//对答案有贡献的分界线cnt++;}while(q--){int k=re();s[k]=s[k]=='L'?'R':'L';//修改操作if(st.find(k)!=st.end())//k是一条分界线左下标{st.erase(k);if(!check[k])cnt--;}if(st.find(k-1)!=st.end()){st.erase(k-1);if(!check[k-1])cnt--;}if(s[k]=='L'&&s[k+1]=='R'){st.insert(k);if(!check[k])cnt++;}if(s[k]=='R'&&s[k-1]=='L'){st.insert(k-1);if(!check[k-1])cnt++;}//更新cntputs(cnt?"NO":"YES");}st.clear();//多测清空}return 0;
}