电影

莫斯科正在举办一个大型国际会议，有 $n$ 个来自不同国家的科学家参会。

每个科学家都只懂得一种语言。

为了方便起见，我们把世界上的所有语言用 $1$ 到 $10^9$ 之间的整数编号。

在会议结束后，所有的科学家决定一起去看场电影放松一下。

他们去的电影院里一共有 $m$ 部电影正在上映，每部电影的语音和字幕都采用不同的语言。

对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影，可以让观影很开心的人最多。

如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

输入格式

第一行输入一个整数 $n$，代表科学家的数量。

第二行输入 $n$ 个整数 $a_1,a_2…a_n$，其中 $a_i$表示 第 $i$ 个科学家懂得的语言的编号。

第三行输入一个整数 $m$，代表电影的数量。

第四行输入 $m$ 个整数 $b_1,b_2…b_m$，其中 $b_i$ 表示第 $i$ 部电影的语音采用的语言的编号。

第五行输入 $m$ 个整数 $c_1,c_2…c_m$，其中 $c_i$表示第 $i$ 部电影的字幕采用的语言的编号。

请注意对于同一部电影来说，$b_i≠c_i$。

同一行内数字用空格隔开。

输出格式

输出一个整数，代表最终选择的电影的编号。电影编号 $1∼m$。

如果答案不唯一，输出任意一个均可。

数据范围

$1≤n,m≤200000$,
$1≤a_i,b_i,c_i≤10^9$

输入样例

3
2 3 2
2
3 2
2 3

输出样例

2

解析

只考虑电影的语言和字幕是否和科学家会的语言一样，看到询问的数据范围 $2 \times 10^5$，而每个数的大小却是 $1 \times 10^9$ 那么久考虑使用离散化。

离散化是指，将一段稀疏的数据变成一段稠密的数据

对应题意，有一个最简单的实现方法，假设会的语言编号为 2 8 1000 100000，那么就可以得到 $f_2 = …,f_8 = …,f_{1000} = …,f_{100000}=…$ 这里的 $f_i$ 为每种语言有多少科学家会，于是我们询问时直接提取就好，但是有个问题 这里编号大小的数据范围为 $[1,10^9]$，直接开这么大的数组就会 MLE。于是考虑离散化

例如，假设我的原数组是 2 8 1000 100000，那么我的新数组就是 1 2 3 4，为了在询问原数组的数时能快速得到新数组的对应值，我们用另外一个数组来储存原数组 即 $a_i$，那么可得 $a_1 = 2,a_2 = 8, a_3 = 1000, a_4 = 100000$ ，该数组满足单调性，那么用二分在这个数组里查询就可以很快得到新数组的值（即查询的下标）。

我们的原问题也可以得到解决，此时我们的 $f_i$ 就变成了 $f_1 = …,f_2 = …,f_3 = …,f_4 = …$ ，离散化后的下标数据范围为 $[1, 2\times 10^5]$ ，很显然 这样开就不会MLE了。

既然不会 MLE 了，我们再来算下时间复杂度。假设总共有 $K$ 种语言，那么每次询问用二分来查询就是 $O(logK)$ 的复杂度，单独查询电影语言的总复杂度就是 $O(mlogK)$，而二分查询需要满足一定的二分性，且科学家的顺序并不影响我们之后的操作，所以我们统计科学家语言的时候只需要将其排序再统计，那么可得总复杂度就是 $O(nlogn +2mlogK )$

这个时间复杂度是可以过的，即使写的杂糅点时间也绰绰有余。

看代码

#include <cstdio>
#include <iostream>
#include <algorithm>
//不想用map和set 也不想记二分函数 那样就不会计算时间复杂度了
//代码写的有点复杂了，懒得优化 看个思路就好 自己写
const int N = 200005;
int arr[N], Sign[N], Newarr[N], RSign[N], answ[N];
bool Vis[N];

int tnt = 1, tot = 0;
int cheak(int x) { //二分寻找离散化之前的原值
	int l = 1, r = tot;
	while(r >= l) {
		int mid = (l + r) >> 1;
		if(x == Sign[mid]) return mid;
		else if(x > Sign[mid]) l = mid + 1;
		else r = mid - 1;
	} return 0;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
	std::sort(arr + 1, arr + 1 + n);
	
	for (int i = 1; i <= n; i++) { //统计每种语言有多少科学家会，离散化原数组
		if(arr[i] == arr[i + 1]) Newarr[tnt]++;
		else Newarr[tnt]++, tnt++;
		
		if(arr[i] != arr[i + 1]) Sign[++tot] = arr[i];
	}
	
	int m, ans = 0, ansx, maxx = 0, twt = 0; bool flag = false;
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) { //询问电影语言
		int x;
		scanf("%d", &x); RSign[i] = x;
		
		ansx = cheak(x); if(ansx == 0) continue;
		if(maxx < Newarr[ansx]) { 
        //因为可能存在多个听得懂语言的科学家数量相同的电影 所以需要记录
			maxx = Newarr[ansx];
			ans = i;
			twt = 1;
			answ[twt] = i;
		} else if(maxx == Newarr[ansx]) {
			twt++;
			answ[twt] = i;
		}
	} if(ans == 0) flag = true;
    //如果所有科学家都听不懂，那么我们就标记 等会儿就只考虑看得懂
	
	for (int i = 1; i <= twt; i++) Vis[answ[i]] = true; //方便调用
	
	int ansy, maxy = 0;
	for (int i = 1; i <= m; i++) { //询问电影字幕
		int y;
		scanf("%d", &y);
		
		ansy = cheak(y); if(ansy == 0) continue;
		if(flag && maxy <= Newarr[ansy]) maxy = Newarr[ansy], ans = i; 
		if(!flag && Vis[i] && maxy <= Newarr[ansy]) {
			maxy = Newarr[ansy];
			ans = i;
		}
	} if(ans == 0) printf("%d\n", m); else printf("%d\n", ans);
    //如果没有一部电影是科学家们看得懂和听得懂的 我们就随便输出一个（也满足题意）
	return 0;
}