主席树启发式合并。
一开始使用树剖LCA没发现出问题了，后来拍了半天才发现，然后换成了倍增。
当然也可以用LCT维护LCA。
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <vector>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e5;
void* allocate();
struct Node {
int begin, end;
Node *left = nullptr, *right = nullptr;
int value;
Node(int_t begin, int_t end) {
this->begin = begin;
this->end = end;
value = 0;
}
int_t query(int_t begin, int_t end) {
if (end < this->begin || begin > this->end) return 0;
if (this->begin >= begin && this->end <= end) return this->value;
return left->query(begin, end) + right->query(begin, end);
}
void maintain() {
if (begin != end) {
this->value = left->value + right->value;
}
}
static Node* build(int begin, int end) {
Node* node = new Node(begin, end);
if (begin != end) {
int mid = (begin + end) / 2;
node->left = build(begin, mid);
node->right = build(mid + 1, end);
}
return node;
}
};
int kth(int k, Node* v1, Node* v2, Node* lca, Node* lcap) {
if (v1->begin == v1->end) return v1->begin;
int_t leftVal = v1->left->value + v2->left->value - lca->left->value -
lcap->left->value;
if (k <= leftVal)
return kth(k, v1->left, v2->left, lca->left, lcap->left);
else
return kth(k - leftVal, v1->right, v2->right, lca->right, lcap->right);
}
Node* buildNext(Node* base, int_t pos, int_t val = 1) {
Node* next = new (allocate()) Node(*base);
if (next->begin == next->end) {
next->value += 1;
} else {
int_t mid = (base->begin + base->end) / 2;
if (pos <= mid)
next->left = buildNext(base->left, pos, val);
else
next->right = buildNext(base->right, pos, val);
next->maintain();
}
return next;
}
int depth[LARGE + 1], parent[LARGE + 1];
int vals[LARGE + 1];
int n, m, t;
int jumpto[21][LARGE + 1];
Node* roots[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];
const int_t SIZE = LARGE * 200;
char buf[SIZE * sizeof(Node)];
int_t used = 0;
void* allocate() {
assert(used < SIZE);
return buf + (used++) * sizeof(Node);
}
namespace UFS {
int_t size[LARGE + 1], parent[LARGE + 1];
void init() {
for (int i = 1; i <= n; i++) {
size[i] = 1;
parent[i] = i;
}
}
int query(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void merge(int a, int b) {
if (size[a] > size[b]) std::swap(a, b);
a = query(a);
b = query(b);
if (a == b) return;
size[b] += size[a];
parent[a] = b;
}
} // namespace UFS
void DFS1(int_t vtx, Node* base, int_t from = -1) {
roots[vtx] = buildNext(base, vals[vtx], 1);
parent[vtx] = from;
if (from <= 0)
jumpto[0][vtx] = -1;
else
jumpto[0][vtx] = from;
for (int_t to : graph[vtx]) {
if (to != from) {
depth[to] = depth[vtx] + 1;
DFS1(to, roots[vtx], vtx);
}
}
}
void DFS2(int vtx, int from, int k) {
if ((1 << k) > depth[vtx])
jumpto[k][vtx] = -1;
else {
jumpto[k][vtx] = jumpto[k - 1][jumpto[k - 1][vtx]];
}
for (auto to : graph[vtx]) {
if (to != from) DFS2(to, vtx, k);
}
}
void link(int v1, int v2) {
if (UFS::size[UFS::query(v1)] > UFS::size[UFS::query(v2)])
std::swap(v1, v2);
graph[v1].push_back(v2);
graph[v2].push_back(v1);
depth[v1] = depth[v2] + 1;
DFS1(v1, roots[v2], v2);
for (int i = 1; i <= 18; i++) DFS2(v1, v2, i);
UFS::merge(v1, v2);
}
int queryLCA(int v1, int v2) {
if (depth[v1] < depth[v2]) std::swap(v1, v2);
int diff = depth[v1] - depth[v2];
for (int i = 18; i >= 0; i--) {
if (diff & (1 << i)) v1 = jumpto[i][v1];
}
if (v1 == v2) return v1;
assert(depth[v1] == depth[v2]);
for (int i = 18; i >= 0; i--) {
if (jumpto[i][v1] != jumpto[i][v2]) {
v1 = jumpto[i][v1];
v2 = jumpto[i][v2];
}
}
assert(parent[v1] == parent[v2]);
return parent[v1];
}
std::vector<int> numbers;
int query(int v1, int v2, int k) {
if (v1 > n || v2 > n) return 0;
if (UFS::query(v1) != UFS::query(v2)) return 0;
auto lca = queryLCA(v1, v2);
if (parent[lca] == -1)
return kth(k, roots[v1], roots[v2], roots[lca], roots[0]);
return kth(k, roots[v1], roots[v2], roots[lca], roots[parent[lca]]);
}
int getRank(int x) {
return std::lower_bound(numbers.begin(), numbers.end(), x) -
numbers.begin() + 1;
}
void process() {
used = 0;
scanf("%d%d%d", &n, &m, &t);
numbers.clear();
for (int i = 1; i <= n; i++) {
scanf("%d", &vals[i]);
numbers.push_back(vals[i]);
}
UFS::init();
std::sort(numbers.begin(), numbers.end());
numbers.resize(std::unique(numbers.begin(), numbers.end()) -
numbers.begin());
for (int i = 1; i <= n; i++) {
vals[i] = getRank(vals[i]);
}
for (int i = 1; i <= m; i++) {
int v1, v2;
scanf("%d%d", &v1, &v2);
graph[v1].push_back(v2);
graph[v2].push_back(v1);
UFS::merge(v1, v2);
}
for (int i = 1; i <= n; i++)
if (roots[i] == nullptr) {
DFS1(i, roots[0]);
//枚举顺序写错了！！
for (int j = 1; j <= 18; j++) DFS2(i, -1, j);
}
int lastans = 0;
for (int i = 1; i <= t; i++) {
char buf[5];
scanf("%s", buf);
if (buf[0] == 'L') {
int v1, v2;
scanf("%d%d", &v1, &v2);
v1 ^= lastans;
v2 ^= lastans;
link(v1, v2);
} else {
int v1, v2, k;
scanf("%d%d%d", &v1, &v2, &k);
v1 ^= lastans;
v2 ^= lastans;
k ^= lastans;
int_t result = query(v1, v2, k);
if (result == 80001) {
cout << 0 << endl;
continue;
}
lastans = numbers[result - 1];
printf("%d\n", lastans);
}
}
}
int main() {
roots[0] = Node::build(1, 8e4 + 1);
int T;
cin >> T;
process();
return 0;
}
发表回复