UVa 11991

Easy Problem from Rujia Liu?

from Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

Problem

给出一个包含n个整数的数组，询问整数v在数组中第k次出现的位置（以1为起点），询问有m次。

（1<=n,m,k<=100,000，1<=v<=1,000,000）

Solution

由于整数v的范围是1<=v<=1,000,000，可以开100W个vector专门用来存放每个数字的第k次出现的位置。当然，100W个vector对内存有一定的挑战。更保险做法是利用一个以v为键，vector为值的map。写法如下： map<int, vector<int> >

预处理的时间复杂度是 O(N·logN) ，查询一次的时间复杂度为 O(logN)。