题解 P5604 【小O与排列】

· · 题解

瞎扯

月赛上肝了一个多小时这个题的具体实现，细节爆炸啊 qaq

做法

做法：线段树+set

考虑一种巧妙的维护：对于每一个 a_i，维护 b_i=\max j<i，使得 a_i 与 a_j 发生关系（可互逆），且 \forall j<k<i,a_k \not =a_i。

那么对于一个询问区间 l,r，因为每一个相同的 a_i 只有第一个对 b_i 有贡献，所以答案即为 \max \{q_i|l\leq i\leq r\}，使用线段树维护，这样就可以通过只有询问的点了。

考虑修改操作，维护 p_i 的逆数组 ap_i，因为是单点修改，只需要更新修改位置后的所有 a_i,p_{a_i},ap_{a_i} 即可，用对每一个值开 set 维护，值的修改使用 .insert()，.erase()，.lower_bound()。更新结束后按照预处理的方法更新即可，时间复杂度 O(n\log n)。

具体细节见代码实现。

强烈建议：一定要写函数！！！！

代码实现

#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
namespace fast_io
{
    char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0;
    in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
    in ll read()
    {
        ll x=0,y=1;while(nc=gc(),(nc<48||nc>57)&&nc!=-1)if(nc==45)y=-1;Bi=1;
        x=nc-48;while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*y;
    }
    in db gf() {re a=read(),b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi):a);}
    in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
    in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
    in void flush() {if(C>1<<22) ot();}
    template <typename T>
    in void write(T x,char t)
    {
        re y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
        if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
    }
    in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=5e5+5;
int n,m,a[N],b[N],ab[N],c[N],p[N],ap[N],mx[N<<2],lst[N];
set<int>s[N];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
in void push_up(re x) {mx[x]=max(mx[ls(x)],mx[rs(x)]);}
void build(re p,re l,re r)
{
    if(l==r) return mx[p]=b[l],void();
    build(ls(p),l,mid);build(rs(p),mid+1,r);push_up(p);
}
void update(re p,re l,re r,re x,re y)
{
    if(l==r) return mx[p]=y,void();
    (x<=mid)?update(ls(p),l,mid,x,y):update(rs(p),mid+1,r,x,y);push_up(p);
}
int query(re p,re l,re r,re ql,re qr)
{
    if(ql<=l&&r<=qr) return mx[p];
    if(ql>mid) return query(rs(p),mid+1,r,ql,qr);
    if(qr<=mid) return query(ls(p),l,mid,ql,qr);
    return max(query(rs(p),mid+1,r,ql,qr),query(ls(p),l,mid,ql,qr));
}
#define lb lower_bound
in void update(re x,re y) {update(1,1,n,x,y);}
in int get(re x)
{
    auto it=s[a[x]].lb(x);re pre=0,pp=0,v=p[a[x]],av=ap[a[x]];
    if(it!=s[a[x]].begin()) pre=*--it;
    if((it=s[v].lb(x))!=s[v].begin()) pp=*--it;
    if((it=s[av].lb(x))!=s[av].begin()) pp=max(pp,*--it);
    return pp>pre?pp:0;
}
in void upd(set<int>::iterator it) {update(*it,b[*it]=get(*it));}
in void erase(re x)
{
    s[a[x]].erase(x),b[x]=0;auto it=s[a[x]].lb(x);re v=p[a[x]],av=ap[a[x]];
    if(it!=s[a[x]].end()) upd(it);
    if((it=s[v].lb(x))!=s[v].end()) upd(it);
    if((it=s[av].lb(x))!=s[av].end()) upd(it);
}
in void add(re x,re y)
{
    a[x]=y,s[a[x]].insert(x);auto it=s[a[x]].lb(x);
    re v=p[a[x]],av=ap[a[x]];upd(it);it++;
    if(it!=s[a[x]].end()) upd(it);
    if((it=s[v].lb(x))!=s[v].end()) upd(it);
    if((it=s[av].lb(x))!=s[av].end()) upd(it);
}
int main()
{
    n=read(),m=read();
    for(re i=1;i<=n;i++) p[i]=read(),ap[p[i]]=i;
    for(re i=1;i<=n;i++) a[i]=read();
    for(re i=1;i<=n;i++) 
    {
        s[a[i]].insert(i);re v=p[a[i]],pp=max(lst[v],lst[ap[a[i]]]);
        if(pp>lst[a[i]]) update(1,1,n,i,b[i]=pp);lst[a[i]]=i;
    }
    build(1,1,n);
    while(m--)
    {
        re op=read(),x=read(),y=read();
        if(op==2) (query(1,1,n,x,y)>=x)?write("Yes"):write("No");
        else erase(x),add(x,y);
    }
    return ot(),0;
}
//Author: disangan233
//In my dream's scene,I can see the everything that in Cyaegha.