CF1093：E. Intersection of Permutations（树状数组套主席树）

题意：给定长度为N的a数组，和b数组，a和b都是1到N的排列；有两种操作，一种是询问[L1,R1]，[L2,R2]；即问a数组的[L1,R1]区间和b数组的[L2,R2]区间出现了多少个相同的数字。一种是修改b数组两个位置的值。

思路：如果把b数组每个数取对应a数组对应数的位置，即按照b的下标建立横坐标，纵坐标是它在a中的位置，那么问题就成了，询问在区间[L2,R2]里面，多少个数在[L1,R1]这区间。这很明显就是主席树可以解决的了。时间复杂度是O(N*logN*logN)；常数差不多是4。

因为空间的问题，但是赛场上不少树套树都MLE或者RE了。

这里学到了回收空间：因为这里的节点不可能出现负数，所以如果一个节点的sum为0，那么子树节点的sum值都为0，那么这个子树都可以回收，即把它们赋值为0；

（cdq先补了G再回来补。分块懒得补了。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

struct in{

    int l,r,sum;

    in(){l=r=sum=;}

}s[maxn*];

queue<int>q;

int rt[maxn],pos[maxn],a[maxn],b[maxn],N,cnt;

void add(int &Now,int L,int R,int pos,int v)

{

    if(!Now){

        if(!q.empty()) Now=q.front(),q.pop();

        else Now=++cnt;

    }

    s[Now].sum+=v;

    if(L==R) return ;int Mid=(L+R)>>;

    if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);

    else add(s[Now].r,Mid+,R,pos,v);

    if(!s[Now].sum) {q.push(Now); Now=;}

}

void Add(int x,int pos,int v)

{

    while(x<=N){

        add(rt[x],,N,pos,v);

        x+=(-x)&x;

    }

}

int query(int Now,int L,int R,int l,int r)

{

    if(L>R) return ;

    if(L<||l<) return ;

    if(!Now) return ;

    if(l<=L&&r>=R) return s[Now].sum;

    int Mid=(L+R)>>,res=;

    if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);

    if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);

    return res;

}

int Query(int x,int L,int R)

{

    if(L>R) return ; if(x<=) return ;

    int res=; while(x){

        res+=query(rt[x],,N,L,R);

        x-=(-x)&x;

    } return res;

}

int main()

{

    int M,opt,L1,R1,L2,R2,x,y;

    scanf("%d%d",&N,&M);

    rep(i,,N) scanf("%d",&a[i]),pos[a[i]]=i;

    rep(i,,N) scanf("%d",&b[i]);

    rep(i,,N) Add(i,pos[b[i]],);

    while(M--){

        scanf("%d",&opt);

        if(opt==){

            scanf("%d%d%d%d",&L1,&R1,&L2,&R2);

            int ans=Query(R2,L1,R1)-Query(L2-,L1,R1);

            printf("%d\n",ans);

        }

        else {

            scanf("%d%d",&x,&y);

            Add(x,pos[b[x]],-); Add(y,pos[b[y]],-);

            swap(b[x],b[y]);

            Add(x,pos[b[x]],); Add(y,pos[b[y]],);

        }

    }

    return ;

}

巴特西

CF1093：E. Intersection of Permutations（树状数组套主席树）

最新文章

热门文章