hello.

题解 CF1093E 【Intersection of Permutations】

2018-12-18 21:52:35


文章首发于 个人博客

思路

看到这道题我第一个想法就是:带修改主席树。

令 $p_i$ 代表 $b_i$ 在 $a$ 中出现的位置,每次询问就是求区间 $[l_b,r_b]$ 中,权值在 $[l_a,r_a]$ 之间的数字个数,修改就是简单的单点修改。

静态主席树的写法大家非常清楚,我把它理解为前缀权值线段树。如何动态维护一个前缀数组呢?采用树状数组即可。我写的带修改主席树本质就是树状数组套主席树,树状数组上每个节点对应储存了相应区间信息的主席树。

这样写实测过不了。原因很简单,空间不够。但是这个东西还是很有用的(我写的也很好看),代码放在文章末尾了。

如何在 Codeforces 上通过此题?把主席树换成 $\text{pbds}$ 里的 红黑树 即可。

代码

以下是在 Codeforces 上可以通过的代码。

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
#define maxn 2000100
#define pi pair<int,int>
#define mp make_pair
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <class T> using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
    return x*flag;
}
template <int size> struct rbtree{
    Tree<int> val[size+1];
    void update(int pos,int tag,int op){
        while(pos<=size){
            if (op) val[pos].insert(tag);
            else val[pos].erase(tag);
            pos+=(pos&-pos);
        }
    }
    int query(int pos,int tag){
        int res=0;
        while(pos){
            res+=val[pos].order_of_key(tag+1);
            pos-=(pos&-pos);
        }
        return res;
    }
    int query(int l,int r,int L,int R){
        return query(r,R)-query(r,L)-query(l,R)+query(l,L);
    }
};
rbtree<maxn>T;
int n,m,a[maxn],b[maxn],p[maxn];
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i)
        a[i]=read(),p[a[i]]=i;
    for (int i=1;i<=n;++i)
        b[i]=read(),b[i]=p[b[i]],T.update(i,b[i],1);
    for (int i=1,op,l,r,L,R;i<=m;++i){
        op=read();
        if (op==1){
            l=read(),r=read(),L=read(),R=read();
            printf("%d\n",T.query(L-1,R,l-1,r));
        }
        if (op==2){
            l=read(),r=read();
            T.update(l,b[l],0);T.update(r,b[r],0);
            swap(b[l],b[r]);
            T.update(l,b[l],1);T.update(r,b[r],1);
        }
    }
} 

以下是带修改主席树,在极限数据下爆空间了。

#include <bits/stdc++.h>
#define maxn 200100
#define mid ((l+r)>>1)
#define logn 100
int rt[maxn],ts[maxn*135],ls[maxn*135],rs[maxn*135];
int a[maxn],b[maxn],A[maxn],B[maxn],C[maxn],la,lb,cnt,n,m;
void update(int &p,int f,int l,int r,int x,int v){
    if (!p) p=++cnt;ts[p]+=v;
    if (l>=r) return;
    if (mid>=x) update(ls[p],p,l,mid,x,v);
    else update(rs[p],p,mid+1,r,x,v);
}
int query(int p,int l,int r,int L,int R){
    if (L<=l&&r<=R) return ts[p];
    if (mid>=R) return query(ls[p],l,mid,L,R);
    if (mid<L) return query(rs[p],mid+1,r,L,R);
    return query(ls[p],l,mid,L,R)+query(rs[p],mid+1,r,L,R);
}
void change(int x,int y){
    int fx=B[x],fy=B[y];
    for (int i=fx;i<=n;i+=(i&-i)) update(rt[i],0,1,n,x,-1);
    for (int i=fy;i<=n;i+=(i&-i)) update(rt[i],0,1,n,y,-1);
    for (int i=fx;i<=n;i+=(i&-i)) update(rt[i],0,1,n,y,1);
    for (int i=fy;i<=n;i+=(i&-i)) update(rt[i],0,1,n,x,1);
    std::swap(B[x],B[y]);
}
void get(int l,int r,int L,int R){
    int sum=0;l--;
    for (int i=l;i;i-=(i&-i)) sum-=query(rt[i],1,n,L,R);
    for (int i=r;i;i-=(i&-i)) sum+=query(rt[i],1,n,L,R);
    printf("%d\n",sum);
}
int main(){
    freopen("test.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=n;++i) scanf("%d",b+i);
    for (int i=1;i<=n;++i) B[b[i]]=i;
    for (int i=1;i<=n;++i) A[i]=B[a[i]];
    for (int i=1;i<=n;++i) C[a[i]]=i;
    for (int i=1;i<=n;++i) B[i]=C[b[i]];
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;j+=(j&-j))
            update(rt[j],0,1,n,A[i],1);
    for (int i=1,op,a,b,c,d;i<=m;++i){
        scanf("%d",&op);
        if (op==2) scanf("%d%d",&a,&b),change(a,b);
        if (op==1) scanf("%d%d%d%d",&a,&b,&c,&d),get(a,b,c,d);
    }
}