[数据结构与算法]【AtCoder Beginner Contest 250】部分题解

E.

题意：
给定两个数组$a$和$b$，长度都为$n$。$Q$次询问，每次给出$x,y$，$a[1...x]$和$b[1...y]$两个序列中的元素构成的数的集合，是否相同。
数据范围：$1\le a_i,b_i\le 10^9,1\le n,Q\le 2\times 10^5,1\le x,y\le n$

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

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
map<int, int> 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;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖