【AtCoder Beginner Contest 250】部分题解

题意：
给定两个数组 a a a和 b b b，长度都为 n n n。 Q Q Q次询问，每次给出 x , y x,y x,y， a [ 1... x ] a[1...x] a[1...x]和 b [ 1... y ] b[1...y] b[1...y]两个序列中的元素构成的数的集合，是否相同。
数据范围： 1 ≤ a i , b i ≤ 1 0 9 , 1 ≤ n , Q ≤ 2 × 1 0 5 , 1 ≤ x , y ≤ n 1leq a_i,b_ileq 10^9, 1leq n,Qleq 2times 10^5,1leq x,yleq n 1≤ai​,bi​≤109,1≤n,Q≤2×105,1≤x,y≤n

题解：
对于数组 a a a的前 i i i个元素，找到这前 i i i个元素都出现在数组 b b b中的最早的位置，记为 p r e B preB preB。
对于数组 b b b的前 i i i个元素，找到这前 i i i个元素都出现在数组 a a a中的最早的位置。记为 p r e A preA preA。
对于每次询问的 x , y x,y x,y，只要保证 p r e A [ y ] ≤ x preA[y]leq x preA[y]≤x且 p r e B [ x ] ≤ y preB[x]leq y preB[x]≤y，则为正确，否则是错误的。

#include
using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
map posA, posB;
int preA[N], preB[N];
int A[N], B[N];
int n, Q, x, y;

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &A[i]); 
		if(!posA[A[i]]) posA[A[i]] = i;
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &B[i]);
		if(!posB[B[i]]) posB[B[i]] = i;
	}
	for(int i = 1; i <= n; ++i) {
		preA[i] = max(preA[i - 1], !posA[B[i]] ? 0x3f3f3f3f : posA[B[i]]);
		preB[i] = max(preB[i - 1], !posB[A[i]] ? 0x3f3f3f3f : posB[A[i]]);
	}
	scanf("%d", &Q);
	while(Q--) {
		scanf("%d%d", &x, &y);
		if(preB[x] <= y && preA[y] <= x) puts("Yes");
		else puts("No");	
	}
}

int main()
{
	int T = 1;
//	scanf("%d", &T);
	for(int i = 1; i <= T; ++i) solve();

	return 0;
}