1 /*
2 题意：n个时刻点，m次时光穿梭，告诉的起点和终点，q次询问，每次询问t时刻t之前有多少时刻点是可以通过两种不同的路径到达
3 思维：对于当前p时间，从现在到未来穿越到过去的是有效的值，排个序，从大到小询问，那么之前添加的穿越点都是有效的，
4 用multiset保存。比赛时想到了排序，但是无法用线段树实现查询，stl大法好！
5 */
6 #include <cstdio>
7 #include <algorithm>
8 #include <cstring>
9 #include <set>
10 #include <iostream>
11 using namespace std;
12
13 const int MAXN = 1e5 + 10;
14 const int INF = 0x3f3f3f3f;
15 struct Year {
16 int u, v;
17 bool operator < (const Year &r) const {
18 return u > r.u;
19 }
20 }y[MAXN];
21 struct Query {
22 int p, id;
23 bool operator < (const Query &r) const {
24 return p > r.p;
25 }
26 }q[MAXN];
27 int ans[MAXN];
28 int a[3];
29 int n, m, l;
30
31 int main(void) { //ZOJ Monthly, July 2015 - H Twelves Monkeys
32 //freopen ("H.in", "r", stdin);
33
34 while (scanf ("%d%d%d", &n, &m, &l) == 3) {
35 for (int i=1; i<=m; ++i) {
36 scanf ("%d%d", &y[i].u, &y[i].v);
37 }
38 for (int i=1; i<=l; ++i) {
39 scanf ("%d", &q[i].p); q[i].id = i;
40 }
41
42 sort (y+1, y+1+m); sort (q+1, q+1+l);
43 multiset<int> S; int j = 1;
44 for (int i=1; i<=l; ++i) {
45 while (j <= m && y[j].u >= q[i].p) {
46 S.insert (y[j].v); j++;
47 }
48 multiset<int>::iterator it; int cnt = 0;
49 for (it=S.begin (); it!=S.end (); ++it) {
50 a[++cnt] = *(it); if (cnt == 2) break;
51 }
52 if (cnt == 2 && a[2] <= q[i].p) ans[q[i].id] = q[i].p - a[2];
53 else ans[q[i].id] = 0;
54 }
55 for (int i=1; i<=l; ++i)
56 printf ("%d
", ans[i]);
57 }
58
59 return 0;
60 }
思维+multiset ZOJ Monthly, July 2015
编译人生，运行世界！