网硕互联帮助中心P3901 数列找不同
题目描述
现有数列
A
1
,
A
2
,
…
,
A
N
A_1,A_2,\\ldots,A_N
A1,A2,…,AN，
Q
Q
Q 个询问
(
L
i
,
R
i
)
(L_i,R_i)
(Li,Ri)，询问
A
L
i
,
A
L
i
+
1
,
…
,
A
R
i
A_{L_i} ,A_{L_i+1},\\ldots,A_{R_i}
ALi,ALi+1,…,ARi 是否互不相同。
输入格式
第一行，两个整数
N
,
Q
N,Q
N,Q。 第二行，
N
N
N 个整数
A
1
,
A
2
,
…
,
A
N
A_1, A_2, \\ldots , A_N
A1,A2,…,AN。 接下来
Q
Q
Q 行，每行两个整数
L
i
,
R
i
L_i,R_i
Li,Ri。
输出格式
对每个询问输出一行，Yes 或 No。
输入输出样例 #1
输入 #1
4 2
1 2 3 2
1 3
2 4
输出 #1
Yes
No
说明/提示
对于
50
%
50\\%
50% 的数据，
N
,
Q
≤
10
3
N,Q \\le 10^3
N,Q≤103。 对于
100
%
100\\%
100% 的数据，
1
≤
N
,
Q
≤
10
5
1 \\le N,Q \\le 10^5
1≤N,Q≤105，
1
≤
A
i
≤
N
1 \\le A_i \\le N
1≤Ai≤N，
1
≤
L
i
≤
R
i
≤
N
1 \\le L_i \\le R_i \\le N
1≤Li≤Ri≤N。
C++实现
#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; —i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = –1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}
const int N = 1e5 + 1e2;
int n, q;
int a[N], Left[N];
int last[N], Max_Left[N];
void input() {
n = read(); q = read();
For (i, 1, n)
a[i] = read();
For (i, 1, n) {
Left[i] = last[a[i]];
last[a[i]] = i;
chkmax(Max_Left[i], Left[i]);
chkmax(Max_Left[i], Max_Left[i–1]);
}
}
void solve() {
while (q—) {
int l = read(), r = read();
puts(Max_Left[r] >= l ? "No" : "Yes");
}
}
int main () {
input();
solve();
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
评论前必须登录！
注册