30pts
暴力搜索
对于每一个 在 里面搜索，如果 答案就加一，搜索完之后输出答案。
时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
long long n, m, q, a[1000050], b[1000050], s[1000050];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (long long i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (long long i = 1; i <= m; ++i) scanf("%d", &b[i]);
while (q--) {
long long x, y, ans = 0;
scanf("%d%d", &x, &y);
for (int i = x; i <= y; i++) {
int f = 1;
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) {
f = 0;
break;
}
}
if (!f)
ans++;
}
printf("%d\n", ans);
}
}
70pts
二分查找
对 数组预处理，先排序然后对于每一个 在 数组里二分查找，能找到就答案加一，循环完之后输出答案。
时间复杂度：
#include <bits/stdc++.h>
using namespace std;
int n, m, q, a[1000050], b[1000050];
bool check(int x) {
int l = 1, r = m;
while (l <= r) {
int mid = (l + r) >> 1;
if (b[mid] < x)
l = mid + 1;
else if (b[mid] > x)
r = mid - 1;
else {
return 1;
}
}
return 0;
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
sort(b + 1, b + 1 + m);
while (q--) {
int x, y, ans = 0;
scanf("%d%d", &x, &y);
for (int i = x; i <= y; i++) {
if (check(a[i]))
ans++;
}
cout << ans << endl;
}
}
100pts
先对 数组排序，然后预处理，对每一个 在 数组里二分查找，能找到就标记为 ，用前缀和处理，查询只要 ，输出 就可以了，但是输入输出需要使用快读或者 ,不然可能会 哦。
其实前缀和也可以用树状数组维护，但是没必要
时间复杂度：
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
int n, m, q, a[1000050], b[1000050], s[1000050];
bool check(int x) {
int l = 1, r = m;
while (l <= r) {
int mid = (l + r) / 2;
if (b[mid] < x)
l = mid + 1;
else if (b[mid] > x)
r = mid - 1;
else if (b[mid] == x)
return 1;
}
return 0;
}
int main() {
n = read();
m = read();
q = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) b[i] = read();
sort(b + 1, b + 1 + m);
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + check(a[i]);
}
while (q--) {
int x, y;
x = read();
y = read();
write(s[y] - s[x - 1]);
cout << "\n";
}
}