1.4 找不同

实验任务

对于一个数组,可以玩很多次找不同;每次提问会给出一个位置范围\([L,R]\)及一个数 \(x\),你要做的是:在数组的第 \(L\) 个数到第 \(R\) 个数中,找出第一个不是 \(x\)的数所在的位置(即它在整个数组中是第几个数)。

数据输入

输入第一行为两个正整数 n,q,表示数组长度及“找不同” 的次数。接下去一行 n 个正整数,表示数组,以空格隔开。接下去 q 行,每行三个正整数 L,R,x,表示一次提问。

数据输出

依次对每个提问输出答案。如果没有满足条件的数,输出” -1” 。

输入示例 输出示例
6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2
2
3
-1
3

数据范围

数组中的元素及每次询问的 \(x\leq 10^9\)\(1\leq L\leq R\leq n\)\(80\%\)的得分点,\(n, q\leq 1000\);其余 \(20\%\)的得分点,\(n, q\leq 200000\)

源代码

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
#include <iostream>
using namespace std;
#define maxn 200005

class Difference{
public:
int data;
int next;
Difference() :data(0), next(-1) {}
};

Difference dif[maxn];

//预处理:连接相邻相同区间,如此查找复杂度降为O(1)
int main(){
int n, q, i;
scanf("%d%d", &n, &q);
for (i = 1; i <= n; ++i)
scanf("%d", &dif[i].data);
for (i = n - 1; i > 0; --i)
dif[i].next = dif[i].data != dif[i + 1].data ? i + 1 : dif[i + 1].next;
int L, R, x;
for (i = 0; i < q; ++i){
scanf("%d%d%d", &L, &R, &x);
if (dif[L].data != x)
printf("%d\n", L);
else
printf("%d\n", dif[L].next <= R ? dif[L].next : -1);
}
return 0;
}

设计思路与复杂度分析

如果枚举\(L\rightarrow R\),最坏情况需要遍历整个数组,然后发现找不到解,复杂度为\(O(n\times q)\)。 最坏情况下,因为相同的值导致需要遍历很多不需要的位置,那么就可以合并位置相邻且数值相同的数为一个数段。这样,如果位置\(L\)的值不是\(x\),则答案就是\(L\),否则答案为下一个数段的起始位置。如果下一个数段超出询问区间则返回\(-1\)。这样预处理之后,查找复杂度降为\(O(1)\),整体复杂度降为\(O(\max(n,q))\)

给博主加鸡腿!
0%