「Two permutations」Solution

简述题意

给定两个长度为 $n$ 的排列 $a,b$，以及 $q$ 次询问，每次询问给定 $l_1,r_1,l_2,r_2$，求出有多少个数 $x$ 满足 $x\in a_i,i\in [l_1,r_1]$ 且 $x\in b_i,i\in [l_2,r_2]$，强制在线。

思路

这种板子题评紫

注意到每个数仅出现一次，所以不妨令 $a_i$ 在 $b$ 排列中出现的位置为 $t{o}_i$，每次查询 $[l_1,r_1]$ 中有多少个 $t{o}_i$ 满足 $l_2\le t{o}_i\le r_2$ 即可。特定区间值域查询，一眼主席树。

代码

注意这道题有点卡空间，不要乱开。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.2e6 + 5;
int n , m , a[MAXN] , b[MAXN] , lastans = -1;
namespace Segement{
	static int tot , rt[MAXN] , root;
	struct tree{
		int l , r , sum , ls , rs;
	}tree[MAXN * 20];
	int build(int p , int l , int r) {
		p = ++ tot;
		tree[p].l = l , tree[p].r = r;
		if (l == r) return p;
		int mid = l + r >> 1;
		tree[p].ls = build(p , l , mid) , tree[p].rs = build(p , mid + 1 , r);
		return p;
	}
	int newnode(int p) {
		tree[++ tot] = tree[p];
		return tot;
	}
	int update(int p , int x) {
		int now = newnode(p);
		tree[now].sum ++;
		if (tree[now].l == tree[now].r) return now;
		int mid = tree[now].l + tree[p].r >> 1;
		if (x <= mid) tree[now].ls = update(tree[now].ls , x);
		else tree[now].rs = update(tree[now].rs , x);
		return now;
	}
	int query(int p , int p2 , int l , int r) {
		if (tree[p].l >= l && tree[p].r <= r) return tree[p2].sum - tree[p].sum;
		int mid = tree[p].l + tree[p].r >> 1 , tmp = 0;
		if (l <= mid) tmp += query(tree[p].ls , tree[p2].ls , l , r);
		if (r > mid) tmp += query(tree[p].rs , tree[p2].rs , l , r);
		return tmp;
	}
}
using namespace Segement;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) cin >> a[i];
	for (int i = 1 , x ; i <= n ; i ++) cin >> x , b[x] = i;
	rt[0] = build(1 , 1 , n);
	for (int i = 1 ; i <= n ; i ++) rt[i] = update(rt[i - 1] , b[a[i]]);
	cin >> m;
	while(m --) {
		int a , b , c , d;
		cin >> a >> b >> c >> d;
		int l1 = (a + lastans) % n + 1 , r1 = (b + lastans) % n + 1;
		int l2 = (c + lastans) % n + 1 , r2 = (d + lastans) % n + 1;
		if (l1 > r1) swap(l1 , r1);
		if (l2 > r2) swap(l2 , r2);
		cout << (lastans = query(rt[l1 - 1] , rt[r1] , l2 , r2)) << '\n';
	}
	return 0;
}