[BZOJ2733] [HNOI2012]永无乡（并查集 + 线段树合并）

传送门

一看到第k大就肯定要想到什么权值线段树，主席树，平衡树之类的

然后就简单了

用并查集判断连通，每个节点建立一颗权值线段树，连通的时候直接合并即可

查询时再二分递归地查找

时间复杂度好像不是很稳定。。。但hzwer都用这种方法水过。。

正解好像是平衡树+启发式合并，以后学TT

#include <cstdio> #include <iostream> #define N 100001 int n, m, q, cnt; int a[N], f[N], sum[N * 20], ls[N * 20], rs[N * 20], root[N], id[N]; inline int read() inline void insert(int &now, int l, int r, int x) int mid = (l + r) >> 1; if(x <= mid) insert(ls[now], l, mid, x); else insert(rs[now], mid + 1, r, x); sum[now] = sum[ls[now]] + sum[rs[now]]; } inline void merge(int &x, int y) sum[x] += sum[y]; merge(ls[x], ls[y]); merge(rs[x], rs[y]); } inline int query(int now, int l, int r, int x) inline int find(int x) int main() for(i = 1; i <= m; i++) } q = read(); while(q) } else } return 0; }

　　

上一篇：[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））

下一篇：[BZOJ1596] [Usaco2008 Jan]电话网络（树形DP || 贪心）

---

线段树 线段树合并