【洛谷P5604】小O与排列

mrsrz 10月 28, 2019

线段树

题目大意：

给定排列 $p$ 和数列 $a$，保证 $p_i\neq i$。

有两个操作：

单点修改 $a$ 的值。
询问 $l,r$ 内是否存在 $i,j$ 满足 $p_{a_i}=a_j$。

题解：

记 $V_i$ 表示 $i$ 前面的离 $i$ 最近的位置 $k$ 满足 $p_{a_k}=a_i$ 或 $p_{a_i}=a_k$。不存在记 $0$。

对于一次查询，我们直接查询区间内 $V_i$ 的最大值，如果最大值在区间内，则存在数对，否则不存在。

但是，这样维护，修改就非常麻烦。

我们发现，如果 $V_i\sim i$ 还存在一个位置 $k$ 满足 $a_i=a_k$，那么查询的时候，如果 $i$ 和 $V_i$ 都在区间内，那么 $k$ 也必定在区间内，这里的贡献就可以算到 $k$ 头上。

因此，我们令 $V_i$ 表示示 $i$ 前面的离 $i$ 最近的位置 $k$ 满足 $p_{a_k}=a_i$ 或 $p_{a_i}=a_k$，且不存在 $k\in(V_i,i)$ 满足 $a_k=a_i$。如果这样的位置不存在则记 $0$。

那么，单点修改时，$V$ 值变动的位置只有常数个。

那么，用set记录每个 $a_i$ 的值的出现位置，单点更新的时候，把这个位置后面的常数个可能更新的位置求出来，重新求一遍 $V$ 值即可。这些操作都可以在set上完成，时间复杂度 $O(\log n)$。

用线段树维护区间最大值即可。时间复杂度 $O(\log n)$。

于是总时间复杂度 $O((n+m)\log n)$。

Code：

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N=5e5+5;
char buf[(int)1e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
int n,m;
int a[N],p[N],ip[N];
int lst[N],d[N<<2],V[N];
void modify(int l,int r,int o,const int&pos,const int&v){
    if(l==r)d[o]=v;else{
        const int mid=l+r>>1;
        if(pos<=mid)modify(l,mid,o<<1,pos,v);else modify(mid+1,r,o<<1|1,pos,v);
        d[o]=max(d[o<<1],d[o<<1|1]);
    }
}
int query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return d[o];else{
        const int mid=l+r>>1;
        if(L<=mid&&mid<R)return max(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
        if(L<=mid)return query(l,mid,o<<1,L,R);return query(mid+1,r,o<<1|1,L,R);
    }
}
namespace sub{
    set<int>st[N];
    inline int getV(int x){
        auto it=st[a[x]].lower_bound(x);
        int pr=0;
        if(it!=st[a[x]].begin())pr=*--it;
        int v=0;
        it=st[p[a[x]]].lower_bound(x);
        if(it!=st[p[a[x]]].begin())v=*--it;
        it=st[ip[a[x]]].lower_bound(x);
        if(it!=st[ip[a[x]]].begin())v=max(v,*--it);
        return v>pr?v:0;
    }
    void erase(int x){
        st[a[x]].erase(x);
        V[x]=0;
        auto it=st[a[x]].lower_bound(x);
        if(it!=st[a[x]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
        it=st[p[a[x]]].lower_bound(x);
        if(it!=st[p[a[x]]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
        it=st[ip[a[x]]].lower_bound(x);
        if(it!=st[ip[a[x]]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
    }
    void add(int x,int v){
        a[x]=v;
        st[a[x]].insert(x);
        auto it=st[a[x]].lower_bound(x);
        modify(1,n,1,*it,V[*it]=getV(*it));
        ++it;
        if(it!=st[a[x]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
        it=st[p[a[x]]].lower_bound(x);
        if(it!=st[p[a[x]]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
        it=st[ip[a[x]]].lower_bound(x);
        if(it!=st[ip[a[x]]].end()){
            modify(1,n,1,*it,V[*it]=getV(*it));
        }
    }
    void work(){
        memset(lst,0,sizeof lst);
        for(int i=1;i<=n;++i){
            st[a[i]].insert(i);
            int v=max(lst[p[a[i]]],lst[ip[a[i]]]);
            if(v>lst[a[i]])
            modify(1,n,1,i,V[i]=v);
            lst[a[i]]=i;
        }
        while(m--){
            int op=readint(),l=readint(),r=readint();
            if(op==1){
                erase(l);
                add(l,r);
            }else{
                int x=query(1,n,1,l,r);
                puts((l<=x&&x<=r)?"Yes":"No");
            }
        }
    }
}
int main(){
    n=readint(),m=readint();
    for(int i=1;i<=n;++i)p[i]=readint();
    for(int i=1;i<=n;++i)a[i]=readint();
    for(int i=1;i<=n;++i)ip[p[i]]=i;
    sub::work();
    return 0;
}