传送门
一看到第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; }
上一篇：[BZOJ1596] [Usaco2008 Jan]电话网络（树形DP || 贪心）
下一篇：[BZOJ1578] [Usaco2009 Feb]Stock Market 股票市场（DP）
线段树 线段树合并
