線段樹合并+離線+啟發式合并
半年前這道題t成狗。。。
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
struct Query {
int v, x, k, id;
bool friend operator < (Query A, Query B)
{
return A.x < B.x;
}
} q[N];
struct edge {
int u, v, w;
bool friend operator < (edge A, edge B)
{
return A.w < B.w;
}
} e[N];
int n, m, Q;
int root[N], h[N], ans[N];
vector<int> vt;
map<int, int> mp;
inline int read()
{
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
namespace seg
{
int cnt;
int lc[N << 2], rc[N << 2], size[N << 2];
void update(int l, int r, int &x, int pos)
{
x = ++cnt;
++size[x];
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) update(l, mid, lc[x], pos);
else update(mid + 1, r, rc[x], pos);
}
int merge(int x, int y)
{
if(!x) return y;
if(!y) return x;
size[x] += size[y];
lc[x] = merge(lc[x], lc[y]);
rc[x] = merge(rc[x], rc[y]);
return x;
}
int query(int l, int r, int x, int rank)
{
if(l == r) return l;
int mid = (l + r) >> 1;
if(size[rc[x]] >= rank) return query(mid + 1, r, rc[x], rank);
else return query(l, mid, lc[x], rank - size[rc[x]]);
}
} using namespace seg;
int main()
{
n = read();
m = read();
Q = read();
for(int i = 1; i <= n; ++i)
{
h[i] = read();
vt.push_back(h[i]);
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());
for(int i = 1; i <= n; ++i)
{
h[i] = lower_bound(vt.begin(), vt.end(), h[i]) - vt.begin() + 1;
update(1, n, root[i], h[i]);
}
for(int i = 1; i <= m; ++i)
{
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
sort(e + 1, e + m + 1);
for(int i = 1; i <= Q; ++i)
{
q[i].v = read();
q[i].x = read();
q[i].k = read();
q[i].id = i;
}
sort(q + 1, q + Q + 1);
int j = 1;
for(int i = 1; i <= Q; ++i)
{
while(e[j].w <= q[i].x && j <= m)
{
if(root[e[j].u] != root[e[j].v]) root[e[j].u] = root[e[j].v] = merge(root[e[j].u], root[e[j].v]);
++j;
}
if(size[root[q[i].v]] < q[i].k) ans[q[i].id] = -1;
else ans[q[i].id] = query(1, n, root[q[i].v], q[i].k);
}
for(int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
return 0;
}
View Code