题解：CF1702C Train and Queries
若干个车站被停靠若干次，第 $i$ 次停靠的站点为 $j$，设 $\forall j \in n$，站点 $j$ 被停靠所对应的集合为 $ {C_i}$。则容易想到，对于每组询问的 $x,y$，若成立则一定满足 $\min \{C_x\} < \max \{C_y\}$。
发现数据范围中 $u_i$ 较大，但是 $n$ 较小，考虑使用 map <int,int> p1,p2 来存储每个站点的最小，最大停靠编号。值得注意的是，因为 unodered_map 的不稳定性，不要去使用它，可能会导致超时。（好像很多人因为这个，赛后被 hack 疯了）
于是，在询问的时候，只要这两个站点被停靠过并且满足 $\min \{C_x\} < \max \{C_y\}$，就输出 YES，否则为 NO。上代码：
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
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,k,a[MAX];
map <int,int> p1,p2;
int main ()
{
t = read ();
while (t--)
{
n = read ();k = read ();
p1.clear ();p2.clear ();
for (int i = 1;i <= n;++i)
{
a[i] = read ();
p1[a[i]] = (!p1[a[i]]) ? i : min (p1[a[i]],i);
p2[a[i]] = (!p2[a[i]]) ? i : max (p2[a[i]],i);
}
for (int i = 1;i <= k;++i)
{
int x = read (),y = read ();
if (p1[x] != 0 && p1[y] != 0 && p1[x] < p2[y]) printf ("YES\n");
else printf ("NO\n");
}
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
