BZOJ 3551「ONTAK2010」Peaks加强版

发表于 | 分类于

真他X的是个弟弟。

初中会嘴巴的东西，高中不会了。

写了骗分，被多组数据雷普了，从75到5。

我谔谔，还事书这题罢，，，

这题大概可以用可持久化并查集套可持久化平衡树或权值线段树啥的做一下（逃

然后我们考虑用一种简单的做法……

如果我们最后的并查集树中只有原图中的点的话，那么很多信息会非常难处理，那么是否可以考虑引入边？

在Kruskal的过程中，边被从小到大加入。那么我们给每个边建一个点，用来维护经过这条边才能联通的点的信息。最后我们会得到一棵满二叉树。

这样的好处事有很多的……首先我们可以把信息维护在边上了。这个题要求\(k\)大，所以我们就用可持久化权值线段树吧，然后每个非叶子结点合并信息的时候直接可持久化的线段树合并就行了。

然后还有一个小好处，就是这棵树显然从叶子向上的边点的权值事单调不降的，这样我们可以直接倍增找到一个最往上的符合限制的祖先，用这个祖先的信息就行了。

代码：

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 200005;
const int maxm = 500005;
int n, m;
struct Edge {
  int u, v, d;
  bool operator <(const Edge &res) const {
    return d < res.d;
  }
};
Edge E[maxm];

const int bufsiz = 1024 * 1024 * 40;
char buf[bufsiz]; char *cur = buf;
void *alloc(size_t size) {
  if(cur - buf + size > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

struct Node {
  int sumv; Node *lc, *rc;
};
Node *nil;
void init_tree() {
  nil = (Node*)alloc(sizeof(Node));
  nil -> sumv = 0; nil -> lc = nil -> rc = nil;
}
Node *alloc_node(int v = 0, Node *lc = nil, Node *rc = nil) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> sumv = v;
  ret -> lc = lc; ret -> rc = rc;
  return ret;
}
Node *gen_chain(int L, int R, int p, int v) {
  if(L == R) {
    return alloc_node(v);
  } else {
    int M = (L + R) / 2;
    Node *lc = nil, *rc = nil;
    if(p <= M) {
      lc = gen_chain(L, M, p, v);
    } else {
      rc = gen_chain(M + 1, R, p, v);
    }
    return alloc_node(v, lc, rc);
  }
}
Node *merge(Node *A, Node *B) {
  if(A == nil) return B;
  if(B == nil) return A;
  Node *lc = merge(A -> lc, B -> lc);
  Node *rc = merge(A -> rc, B -> rc);
  Node *ret = alloc_node(A -> sumv + B -> sumv, lc, rc);
  return ret;
}
int kth(Node *o, int L, int R, int k) {
  if(o -> sumv < k) {
    return 0;
  }
  if(L == R) {
    return L;
  } else {
    int M = (L + R) / 2;
    if(k <= o -> rc -> sumv) {
      return kth(o -> rc, M + 1, R, k);
    } else {
      return kth(o -> lc, L, M, k - o -> rc -> sumv);
    }
  }
}

int p[maxn];
void init_set() {
  for(int i = 1; i <= 2 * n; i ++) {
    p[i] = i;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void merge_set(int x, int y) {
  x = get_fa(x), y = get_fa(y);
  p[x] = y;
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}

int h[maxn], h2[maxn]; int lsiz;
void desc() {
  std::copy(h + 1, h + 1 + n, h2 + 1);
  std::sort(h2 + 1, h2 + 1 + n);
  lsiz = std::unique(h2 + 1, h2 + 1 + n) - h2 - 1;
  for(int i = 1; i <= n; i ++) {
    h[i] = std::lower_bound(h2 + 1, h2 + 1 + lsiz, h[i]) - h2;
  }
}

int lim[maxn];
int anc[maxn][19]; int cnt;
Node *T[maxn];
void build_tree() {
  memset(anc, -1, sizeof(anc));
  init_set(); init_tree(); desc();
  for(int i = 1; i <= n; i ++) {
    T[i] = gen_chain(1, lsiz, h[i], 1);
  }
  std::sort(E + 1, E + 1 + m); cnt = n;
  for(int i = 1; i <= m; i ++) {
    int u = E[i].u, v = E[i].v, l = E[i].d;
    if(is_same(u, v)) continue;
    u = get_fa(u); v = get_fa(v);
    cnt ++; lim[cnt] = l;
    T[cnt] = merge(T[u], T[v]);
    anc[u][0] = anc[v][0] = cnt;
    merge_set(u, cnt); merge_set(v, cnt);
  }
  for(int j = 1; (1 << j) < cnt; j ++) {
    for(int i = 1; i <= cnt; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) anc[i][j] = anc[a][j - 1];
    }
  }
}
int get_up(int x, int l) {
  for(int j = 18; j >= 0; j --) {
    int a = anc[x][j];
    if(a != -1 && lim[a] <= l) {
      x = a;
    }
  }
  return x;
}

int main() {
  int q; scanf("%d%d%d", &n, &m, &q);
  for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].d);
  }
  build_tree();
  int lastans = 0;
  h2[0] = -1;
  while(q --) {
    int v, x, k; scanf("%d%d%d", &v, &x, &k);
    if(lastans != -1) {
      v ^= lastans;
      x ^= lastans;
      k ^= lastans;
    }
    v = get_up(v, x);
    printf("%d\n", lastans = h2[kth(T[v], 1, lsiz, k)]);
#ifdef LOCAL
    lastans = 0;
#endif
  }
  return 0;
}