[CF2030D] QED's Favorite Permutation 题解

· · 题解

Solution

首先我们可以发现题目给出的两种转移实际上都是双向的，因此可以考虑排列中的每个元素所能到达的位置，构造无向图；对于每个位置，若 s_i = L，连边 i \leftrightarrow i-1，否则连边 i \leftrightarrow i+1。

注意到给定的 s 中存在的形如 LR 的子串将图分割成若干个连通块；若排列可以通过交换被单调递增排序，则对于每个连通块 [l,r]，\{ p_l,p_{l+1},\cdots,p_r \} 排序后得到的序列必然为 \{ l,l+1,\cdots,r\}。

那么对于每次修改，只需要维护连通块的变化并且判断每个连通块是否符合条件即可；对于连通块的维护，可以使用 ODT 维护区间的合并与分裂；快速判断连通块是否满足条件可以通过和哈希解决，用 set 存储所有不合法的连通块即可。

同时，可以注意到在本题中如果维护连通块的元素和，必然不存在两组不同的排列使得所有连通块的的元素和都与元素下标之和相等；因此也可以直接维护前缀和判断是否满足条件而不必使用和哈希（本人太菜了没看出来）。

Code

#include<bits/stdc++.h>
#define loop(x,l,r) for(ll (x) = (l);(x)<=(r);++(x))
#define rloop(x,l,r) for(ll (x) = (r);(x)>=(l);--(x))
#define elif else if
using namespace std;
using ll = long long;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
const ll N=2e5+5;
const ll mod=1e9+7,M=30;
char s[N];
ll p[N],n,q;
struct _hash
{
    ll _val[M];
    _hash(){loop(i,0,M-1)_val[i]=0;}
    _hash(ll x){_val[0]=1;loop(i,1,M-1)_val[i]=(_val[i-1]*x)%mod;}
    inline _hash operator+(const _hash& hs)
    {
        _hash res;
        loop(i,0,M-1)res._val[i]=(_val[i]+hs._val[i])%mod;
        return res;
    }
    inline _hash operator-(const _hash& hs)
    {
        _hash res;
        loop(i,0,M-1)res._val[i]=(_val[i]-hs._val[i]+mod)%mod;
        return res;
    }
    inline bool operator==(const _hash& hs)
    {
        loop(i,0,M-1)if(_val[i]!=hs._val[i])return 0;
        return 1;
    }
}hs1[N],hs2[N];
set<ll> odt,unv;
void solve()
{
    odt.clear();
    unv.clear();
    n=read(),q=read();
    loop(i,0,n+1)hs1[i]=_hash(),hs2[i]=_hash();
    loop(i,1,n)p[i]=read(),hs1[i]=hs1[i-1]+_hash(p[i]);
    loop(i,1,n)hs2[i]=hs2[i-1]+_hash(i);
    odt.insert(n+1);
    odt.insert(1);
    scanf("%s",s+1);
    loop(i,1,n-1)
    {
        if(s[i]=='L'&&s[i+1]=='R')
        {
            odt.insert(i+1);
            auto it=odt.lower_bound(i+1);
            it--;
            ll pre=*it;
            if(hs1[i]-hs1[pre-1]==hs2[i]-hs2[pre-1]);
            else unv.insert(pre);
        }
    }
    auto _it=odt.lower_bound(n+1);
    _it--;
    ll _pre=*_it;
    if(hs1[n]-hs1[_pre-1]==hs2[n]-hs2[_pre-1]);
    else unv.insert(_pre);
    while(q--)
    {
        ll p=read();
        if(s[p]=='L'&&s[p+1]=='R')
        {
            assert(odt.count(p+1));
            auto it=odt.lower_bound(p+1);
            auto itn=it;
            it--,itn++;
            ll pre=*it,nxt=*itn;
            unv.erase(p+1);
            unv.erase(pre);
            odt.erase(p+1);
            if(hs1[nxt-1]-hs1[pre-1]==hs2[nxt-1]-hs2[pre-1]);
            else unv.insert(pre);
        }
        if(s[p]=='R'&&s[p-1]=='L')
        {
            assert(odt.count(p));
            auto it=odt.lower_bound(p);
            auto itn=it;
            it--,itn++;
            ll pre=*it,nxt=*itn;
            unv.erase(p);
            unv.erase(pre);
            odt.erase(p);
            if(hs1[nxt-1]-hs1[pre-1]==hs2[nxt-1]-hs2[pre-1]);
            else unv.insert(pre);
        }
        if(s[p]=='L'&&s[p-1]=='L')
        {
            odt.insert(p);
            auto it=odt.lower_bound(p);
            auto itn=it;
            it--,itn++;
            ll pre=*it,nxt=*itn;
            unv.erase(pre);
            if(hs1[nxt-1]-hs1[p-1]==hs2[nxt-1]-hs2[p-1]);
            else unv.insert(p);
            if(hs1[p-1]-hs1[pre-1]==hs2[p-1]-hs2[pre-1]);
            else unv.insert(pre);
        }
        if(s[p]=='R'&&s[p+1]=='R')
        {
            odt.insert(p+1);
            auto it=odt.lower_bound(p+1);
            auto itn=it;
            it--,itn++;
            ll pre=*it,nxt=*itn;
            unv.erase(pre);
            if(hs1[nxt-1]-hs1[p]==hs2[nxt-1]-hs2[p]);
            else unv.insert(p+1);
            if(hs1[p]-hs1[pre-1]==hs2[p]-hs2[pre-1]);
            else unv.insert(pre);
        }
        if(s[p]=='L')s[p]='R';
        else s[p]='L';
        puts(unv.size()?"No":"Yes");
    }
}
signed main()
{
    ll T=read();
    while(T--)solve();
    return 0;
}