CodeForces#323 C.Two permutations

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

B.Two Permutations

题面

~~这次我不想搬英文题面了，我懒一次吧，毕竟是fateice大佬给的翻译~~

简要翻译

给你两个长度为n的排列，多次询问在第一个排列的[l1,r1]和第二个排列的[l2,r2]同时出现的数有多少个。

Input

第一行包含一个整数$n$，即两个排列中的元素数。下一行包含$n$个整数，用空格分隔: $p_1, p_2 … p_n$ ，代表序列$1$。下一行包含$n$个整数，用空格分隔:$q_1,q_2…q_n$，代表序列$2$。

下面一行包含一个整数$m$，代表询问的次数。

下面的m行包含一行查询的描述。第i个询问的描述由4个整数组成:$a,b,c, d$。查询参数$l_1、r_1、1_2、r_2$由数字$a,b,c,d$通过以下算法得到

引入变量$x$。如果它是第一个查询，那么变量$x=0$，否则它等于前一个查询的值加上$1$。
引入函数$f(z) =((z-1+c)\ mod\ n)+1$。
假设$l_1 = min (f (a), f (b)), r_1 = max(f (a), f (b)), l_2 = min (f (c), f (d)), r_2=max(f (c), f (d))$

Output

对于每个查询输出一行一个整数代表答案。

Sample Input 1

3
3 1 2
3 2 1
1
1 2 3 3

Sample Output 1

Sample Input 2

4
4 3 2 1
2 3 4 1
3
1 2 3 4
1 3 2 1
1 4 2 3

Sample Output 2

Hint

$1\le n\le 10^6$，$1 \le m \le 2×10^5$。

$1\le p_i\le n$，$1\le a,b,c,d\le n$。

我们求出第二个排列的数在第一个排列中所对应的位置。

用可持久化的权值线段树来维护。

时间复杂度$O(mlogm)$

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N=1e6+10;
const int M=2e5+10;
struct seg_tree
{
	int l,r;
	int s;
}t[N*22];
int rot[M<<4],cnt,n,q,answer,pos[M<<4],a[M<<4];

void insert(int &root,int l,int r,int posi,int last)
{
	root=++cnt;
	t[root].l=t[last].l,t[root].r=t[last].r;
	t[root].s=t[last].s+1;
	if(l==r) return;
	int mid=l+r>>1;
	if(posi<=mid) insert(t[root].l,l,mid,posi,t[last].l);
	if(posi>mid) insert(t[root].r,mid+1,r,posi,t[last].r);
}
int query(int root,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr) return t[root].s;
	int mid=l+r>>1,A=0;
	if(ll<=mid) A+=query(t[root].l,l,mid,ll,rr);
	if(rr>mid) A+=query(t[root].r,mid+1,r,ll,rr);
	return A;
}
int get_read()
{
	return (read()+answer-1)%n+1;
}
int main(int argc, char const *argv[])
{
	n=read();
	for(register int i=1,x;i<=n;++i) x=read(),pos[x]=i;
	for(register int i=1,x;i<=n;++i) x=read(),a[i]=pos[x];
	for(register int i=1;i<=n;++i) insert(rot[i],1,n,a[i],rot[i-1]);
	q=read();
	while(q--)
	{
		int A=get_read(),B=get_read(),C=get_read(),D=get_read();
		if(A>B) swap(A,B);
		if(C>D) swap(C,D);
		printf("%d\n",answer=query(rot[D],1,n,A,B)-query(rot[C-1],1,n,A,B));
		++answer;
	}
	return 0;
}