题解：UVA11991 Easy Problem from Rujia Liu?

UVA11991 Easy Problem from Rujia Liu?

刘汝佳的简单题

题目大意

给定一列数，给出若干次询问，每次询问从左到右第 $k$ 个 $u$ 的下标。

解题思路

数据范围较大，直接用 $\mathcal O(n^2)$ 的 ad-hoc 会超时。考虑使用邻接表优化，将复杂度降至 $\mathcal O(n)$。

对每一个数建立一个邻接表，第 $k$ 位存储这个数第 $k$ 次出现的下标，每次查询可以 $\mathcal O(1)$ 完成。详见代码。

参考代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
//#include<unordered_map>
//#define map unordered_map
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
using namespace std;
/*================*/

inline int read() {
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

int n, m;
int x, y;
vector<int> pos[1000005];

signed main() {
	while (scanf("%d%d", &n, &m) == 2) {
		for (auto i : pos)
			i.clear();
		for (int i = 1; i <= n; i++)
			pos[read()].push_back(i);
		while (m--) {
			r(x); r(y);
			if (x > pos[y].size()) {
				puts("0");
				continue;
			}
			printf("%d\n", pos[y][x - 1]);
		}
	}
	return 0;
}