题解 CF323C Two permutations

发表于 分类于 阅读次数： Valine： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

话说这题怎么评到黑的？？

我们可以把第二个排列中的数在第一个排列中出现的位置都处理出来。

然后对于每个询问，答案就变成了第二个序列中 [l2,r2][l_2,r_2] 这个区间内，在第一个序列中位置处于 [l1,r1][l_1,r_1] 的数的个数。

我们以第二个排列的下标为版本，以对应的第一个排列中的位置为下标建立一棵可持久化线段树。

具体就是扫一遍这个序列，对于序列中的每一个数都在前一个数的基础上新建一个版本，以这个数为下标在这个版本上 +1+1。然后答案就是版本 r2r_2 与版本 l2−1l_2-1 中询问 [l1,r1][l_1,r_1] 这两个区间的区间和做差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=1e6+5;
int n,a[N],b[N],tmp[N],m;
struct Segment{
    int val,ls,rs;
}t[N*32];
int rt[N];
int lst=0;
int tot=0;
int f(int x) {
    return (x+lst-1)%n+1;
}
void modify(int &p,int q,int l,int r,int val) {
    p=++tot;
    t[p].ls=t[q].ls;
    t[p].rs=t[q].rs;
    t[p].val=t[q].val+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(val<=mid) modify(t[p].ls,t[q].ls,l,mid,val);
    else modify(t[p].rs,t[q].rs,mid+1,r,val);
}
int query(int p,int l,int r,int ql,int qr) {
    if(ql<=l&&r<=qr) return t[p].val;
    int mid=(l+r)>>1,ans=0;
    if(ql<=mid) ans+=query(t[p].ls,l,mid,ql,qr);
    if(mid<qr) ans+=query(t[p].rs,mid+1,r,ql,qr);
    return ans;
}
int main() {
    scanf("%d",&n);
    rep(i,1,n) {
        scanf("%d",&a[i]);
        tmp[a[i]]=i;
    }
    rep(i,1,n) {
        scanf("%d",&b[i]);
        a[i]=tmp[b[i]];
        modify(rt[i],rt[i-1],1,n,a[i]);
    }
    scanf("%d",&m);
    rep(i,1,m) {
        int l1,l2,r1,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        l1=f(l1),l2=f(l2),r1=f(r1),r2=f(r2);
        if(l1>r1) swap(l1,r1);
        if(l2>r2) swap(l2,r2);
        lst=query(rt[r2],1,n,l1,r1)-query(rt[l2-1],1,n,l1,r1);
        printf("%d\n",lst);
        ++lst;
    }
    return 0;
}