「统计」离散化+Map

发表于 | 分类于

给定N个数，有M个询问。每次询问一段区间内有没有出现过Xi这个数。

输入格式

第一行一个整数N。
第二行N个正整数表示给定的N个数。
第三行一个整数M。
以下M行每行三个整数li，ri和Xi；表示询问区间是[li, ri]，询问数字是Xi。

输出格式

对于每一次询问，输出一个字符。0表示没出现，1表示出现了。

样例输入

1
2
3
4
5
6
7
8
5
1234567 666666 3141593 666666 4343434
5
1 5 3141593
1 5 578202
2 4 666666
4 4 7135610
1 1 1234567

样例输出

10101

数据说明

40%的数据满足：N≤1000，M≤10001

100%的数据满足：N≤10e9，M≤10e5，Xi≤10e9

这道题有很多种解法，在这里介绍一个用map离散化的做法；其实数据够良心，直接for循环打暴力也可以得到40分的（亲测）；

用map（stl）储存数据，以数字为标志，再开一个vector数组存该数据出现过的位置，直接看位置数据内是否有存在所输入查询范围内的个体；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
int n, m, l, r, x, y;
inline int read() {
	char ch = getchar(); int res = 0; int flag = 1;
	while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {res = res * 10 + ch - '0'; ch = getchar();}
	return (res * flag);
}
//高天宇快读；
map < int, vector<int> > mapp;
//用int型映射一个int类型的vector；
inline bool query(int l, int r, int x) {
	for(int i = 0; i < mapp[x].size(); i++) {
		if(mapp[x][i] >= l && mapp[x][i] <= r) return 1;
	}
	return false;
}
int main() {
	freopen("statistic.in", "r", stdin);
	freopen("statistic.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; i++) {
		y = read();
		mapp[y].push_back(i);
	}
	m = read();
	for(int i = 1; i <= m; i++) {
		l = read(); r = read(); x = read();
		if(query(l, r, x)) printf("1");
		else printf("0");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}