首页 > 代码库 > bzoj 2733 永无乡 - 并查集 - 线段树
bzoj 2733 永无乡 - 并查集 - 线段树
<style></style>
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000 对于 100%的数据 n≤100000,m≤n，q≤300000
Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
Sample Input
5 1 4 3 2 5 1 1 2 7Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3
Sample Output
-12512
题目大意 给出n个点和m条边，每个点有个点权，范围为1 ~ n，且没有重复。操作有两种，第一种是联通两个点，第二种是查询点i所在的连通块内第k小的点的编号。
显然会用到并查集，关键在于合并数据，如果开数组 + 归并是铁定的O(n)，但如果至于线段树合并 + 暗黑剪枝兴许可以卡过去。
当插入树或被插入树为空，就可以修改下指针什么的，然后return了。
Code
1 /** 2 * bzoj 3 * Problem#2733 4 * Accepted 5 * Time:2352ms 6 * Memory:26304k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const signed long long llf = (signed long long)((1ull << 63) - 1); 33 const double eps = 1e-6; 34 const int binary_limit = 128; 35 #define smin(a, b) a = min(a, b) 36 #define smax(a, b) a = max(a, b) 37 #define max3(a, b, c) max(a, max(b, c)) 38 #define min3(a, b, c) min(a, min(b, c)) 39 template<typename T> 40 inline boolean readInteger(T& u){ 41 char x; 42 int aFlag = 1; 43 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 44 if(x == -1) { 45 ungetc(x, stdin); 46 return false; 47 } 48 if(x == ‘-‘){ 49 x = getchar(); 50 aFlag = -1; 51 } 52 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u * 10) + x - ‘0‘); 53 ungetc(x, stdin); 54 u *= aFlag; 55 return true; 56 } 57 58 typedef class SegTreeNode { 59 public: 60 int s; 61 SegTreeNode *l, *r; 62 63 SegTreeNode():s(0), l(NULL), r(NULL) { } 64 SegTreeNode(int s, SegTreeNode* l, SegTreeNode* r):s(s), l(l), r(r) { } 65 66 inline void pushUp() { 67 s = l->s + r->s; 68 } 69 }SegTreeNode; 70 71 #define Limit 2000000 72 SegTreeNode pool[Limit]; 73 int top = 0; 74 SegTreeNode null = SegTreeNode(0, &null, &null); 75 76 inline SegTreeNode* newnode() { 77 if(top >= Limit) { 78 return new SegTreeNode(0, &null, &null); 79 } 80 pool[top].l = &null, pool[top].r = &null; 81 return pool + (top++); 82 } 83 84 #define null &null 85 86 typedef class union_found { 87 public: 88 int* f; 89 SegTreeNode** rts; 90 91 union_found():f(NULL), rts(NULL) { } 92 union_found(int n, int* lis) { 93 f = new int[(const int)(n + 1)]; 94 rts = new SegTreeNode*[(n + 1)]; 95 for(int i = 1; i <= n; i++) 96 f[i] = i; 97 for(int i = 1; i <= n; i++) { 98 rts[i] = null; 99 update(rts[i], 1, n, lis[i]);100 }101 }102 103 void update(SegTreeNode*& node, int l, int r, int idx) {104 if(node == null) node = newnode();105 if(l == idx && r == idx) {106 node->s++;107 return;108 }109 int mid = (l + r) >> 1;110 if(idx <= mid) update(node->l, l, mid, idx);111 else update(node->r, mid + 1, r, idx);112 node->pushUp(); 113 }114 115 void merge(SegTreeNode*& a, SegTreeNode*& b) { // Make segment tree b into a.116 if(b == null)117 return;118 if(a == null) {119 a = b;120 return;121 }122 a->s += b->s;123 merge(a->l, b->l);124 merge(a->r, b->r);125 a->pushUp();126 }127 128 int kth(SegTreeNode* node, int l, int r, int k) {129 if(node == null)130 return -1;131 if(l == r && k == 1)132 return l;133 int ls = node->l->s, mid = (l + r) >> 1;134 if(k <= ls)135 return kth(node->l, l, mid, k);136 else137 return kth(node->r, mid + 1, r, k - ls);138 }139 140 int find(int x) {141 return (f[x] == x) ? (x) : (f[x] = find(f[x]));142 }143 144 void unit(int fa, int so) {145 if(isConnected(fa, so)) return;146 int ffa = find(fa);147 int fso = find(so);148 merge(rts[ffa], rts[fso]);149 f[fso] = ffa;150 }151 152 boolean isConnected(int a, int b) {153 return find(a) == find(b);154 }155 156 int query(int x, int n, int k) {157 return kth(rts[find(x)], 1, n, k);158 } 159 }union_found;160 161 int n, m, q;162 int* imp;163 int* keyer;164 union_found uf;165 166 inline void init() {167 readInteger(n);168 readInteger(m);169 imp = new int[(n + 1)];170 keyer = new int[(n + 1)];171 for(int i = 1; i <= n; i++)172 readInteger(imp[i]), keyer[imp[i]] = i;173 uf = union_found(n, imp);174 for(int i = 1, a, b; i <= m; i++) {175 readInteger(a);176 readInteger(b);177 uf.unit(a, b);178 }179 }180 181 inline void solve() {182 readInteger(q);183 char buf[10];184 int a, b;185 while(q--) {186 scanf("%s%d%d", buf, &a, &b);187 if(buf[0] == ‘B‘) {188 uf.unit(a, b);189 } else {190 int res = uf.query(a, n, b);191 if(res == -1)192 puts("-1");193 else194 printf("%d\n", keyer[res]);195 }196 }197 }198 199 int main() {200 init();201 solve();202 return 0;203 }
bzoj 2733 永无乡 - 并查集 - 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。