Though Rujia Liu usually sets hard problems for contests (for example, regional
contests like Xi’an 2006, Beijing 2007 and Wuhan 2009, or UVa OJ contests like
Rujia Liu’s Presents 1 and 2), he occasionally sets easy problem (for example, ‘the
Coco-Cola Store’ in UVa OJ), to encourage more people to solve his problems :D
Given an array, your task is to find the k-th occurrence (from left to right) of an integer v. To make
the problem more difficult (and interesting!), you’ll have to answer m such queries.
Input
There are several test cases. The first line of each test case contains two integers n, m (1 n; m
100; 000), the number of elements in the array, and the number of queries. The next line contains n
positive integers not larger than 1,000,000. Each of the following m lines contains two integer k and v
(1 k n, 1 v 1; 000; 000). The input is terminated by end-of-file (EOF).
Output
For each query, print the 1-based location of the occurrence. If there is no such element, output ‘0’
instead.
Sample Input
8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2
Sample Output
2
0
7
0
思路很简单，但是直接开数组会超内存，一开始使用的vector也还是超内存
后来看大白书才发现要用map，map与vector结合成为一个变长数组
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
#define LS 2*i
#define RS 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
map<int,vector<int> > mat;
int a;
int main()
{
int n,m,i,j,k,v;
while(~scanf("%d%d",&n,&m))
{
for(i = 1;i<=n;i++)
{
scanf("%d",&a);
if(!mat.count(a)) mat[a] = vector<int>();
mat[a].push_back(i);
}
while(m--)
{
scanf("%d%d",&k,&v);
if(!mat.count(v) || mat[v].size()<k) printf("0\n");
else printf("%d\n",mat[v][k-1]);
}
}
return 0;
}