天津大学 2010 年区域赛 1007 Giant For

发表于 分类于

这题典型的线段树加离散化，比赛的时候没有思路，中午突然想到了怎么实现。

这题主要的思路是将全部的数据读取进来然后离线处理，离散化的时候把不同的点按照先 xx 后 yy 的方式离散化，也就是说只要两个点不是同一个点，那么他们的离散化后的 hash 值就不一样，将离散化后的值放到 lst 数组中去。

在线段树中维护第 ii 个 lstlst 元素是否存在，如果存在，那么线段树中的第 ii 个元素值就是 lst[i]lst[i] 对应的 yy 值，否则就为 −1-1，segseg 的值记录 [l,r][l,r] 区间的最大值。每次 find 的时候，读取的如果是 x,yx, y，那么去找 [x+1,M][x+1,M] 区间，优先找左边的区间，如果左边区间的最大值比 yy 来的大，那么解一定在左边区间，如果左边区间的最大值小于或等于 yy，那么用同样的方法找右区间，如果依然没有比 yy 大的，那么返回 −1-1，否则返回第一个比 yy 大的区间在 lstlst 数组中对应的脚标。

主要是离散化的方式有点特别，先按 xyxy 排序，记录 lstlst 数组，然后按 idid 排序，返回原来输入的顺序，这样保证了读取的顺序和输入顺序一致。

我的代码：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
const int MAX = 200100;
struct Lst {
  int x, y;
} lst[MAX];

struct Node {
  int op;
  int x, y;
  int id;
  int val;
  int nxt;
} node[MAX];
int n, M;
int seg[4 * MAX];

bool comp1(const Node& a, const Node& b) {
  if (a.x != b.x)
    return a.x < b.x;
  else
    return a.y < b.y;
}

bool comp2(const Node& a, const Node& b) { return a.id < b.id; }

void hash() {
  for (int i = 0; i < n; i++) node[i].id = i;
  sort(node, node + n, comp1);
  M = 1;
  node[0].val = M;
  lst[M].x = node[0].x;
  lst[M].y = node[0].y;
  for (int i = 1; i < n; i++) {
    if (node[i].x == node[i - 1].x && node[i].y == node[i - 1].y)
      node[i].val = M;
    else {
      node[i].val = ++M;
      lst[M].x = node[i].x;
      lst[M].y = node[i].y;
    }
  }
  node[n - 1].nxt = -1;
  for (int i = n - 2; i >= 0; i--) {
    if (node[i].x != node[i + 1].x)
      node[i].nxt = node[i + 1].val;
    else
      node[i].nxt = node[i + 1].nxt;
  }
  sort(node, node + n, comp2);
}

void init(int k, int l, int r) {
  if (l == r) {
    seg[k] = 0;
    return;
  }
  int mid = (l + r) / 2;
  init(2 * k, l, mid);
  init(2 * k + 1, mid + 1, r);
  seg[k] = 0;
}

void update(int k, int l, int r, int idx, int v) {
  if (l == r) {
    seg[k] = v;
    return;
  }
  int mid = (l + r) / 2;
  if (idx <= mid)
    update(2 * k, l, mid, idx, v);
  else
    update(2 * k + 1, mid + 1, r, idx, v);
  seg[k] = max(seg[2 * k], seg[2 * k + 1]);
}

int read(int k, int l, int r, int a, int b, int v) {
  int tmp;
  int mid = (l + r) / 2;
  if (l > b || r < a) return -1;
  if (seg[k] <= v) return -1;
  if (l == r) return l;
  if (l >= a && r <= b) {
    if (seg[2 * k] > v)
      return read(2 * k, l, mid, a, b, v);
    else
      return read(2 * k + 1, mid + 1, r, a, b, v);
  }
  tmp = read(2 * k, l, mid, a, b, v);
  if (tmp >= 0) return tmp;
  tmp = read(2 * k + 1, mid + 1, r, a, b, v);
  if (tmp >= 0) return tmp;
  return -1;
}

int main() {
  char op[100];
  int id;
  int cnt = 1;
  while (scanf("%d", &n), n) {
    if (cnt != 1) printf("\n");
    for (int i = 0; i < n; i++) {
      scanf("%s%d%d", op, &node[i].x, &node[i].y);
      if (op[0] == 'a')
        node[i].op = 1;
      else if (op[0] == 'r')
        node[i].op = 2;
      else
        node[i].op = 3;
    }
    hash();
    init(1, 1, M);
    printf("Case %d:\n", cnt++);
    for (int i = 0; i < n; i++) {
      switch (node[i].op) {
        case 1:
          update(1, 1, M, node[i].val, node[i].y);
          break;
        case 2:
          update(1, 1, M, node[i].val, -1);
          break;
        case 3:
          if (node[i].nxt < 0) {
            printf("-1\n");
            break;
          }
          id = read(1, 1, M, node[i].nxt, M, node[i].y);
          if (id < 0)
            printf("-1\n");
          else
            printf("%d %d\n", lst[id].x, lst[id].y);
          break;
      }
    }
  }
  return 0;
}

看来还是见世面见的太少了，很多算法没有思路。