[BZOJ3545] [ONTAK2010]Peaks（线段树合并 + 离散化）

传送门

由于困难值小于等于x这个很恶心，可以离线处理，将边权，和询问时的x排序。

每到一个询问的时候，将边权小于等于x的都合并起来再询问。

。。

有重复元素的线段树合并的时间复杂度是nlog^2n

#include <cstdio> #include <iostream> #include <algorithm> #define N 500001 int n, m, q, cnt, tot, size; int sum[N * 10], ls[N * 10], rs[N * 10], a[N], b[N], f[N], root[N], ans[N], c[N << 1]; struct node }p[N], ask[N]; inline int read() inline bool cmp1(node x, node y) inline bool cmp2(node x, node y) inline void merge(int &x, int y) sum[x] += sum[y]; merge(ls[x], ls[y]); merge(rs[x], rs[y]); } 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 int query(int now, int l, int r, int x) inline int find(int x) int main() for(i = 1; i <= m; i++) for(i = 1; i <= q; i++) std::sort(c + 1, c + m + q + 1); tot = std::unique(c + 1, c + m + q + 1) c 1; for(i = 1; i <= m; i++) p[i].z = std::lower_bound(c + 1, c + tot + 1, p[i].z) c; for(i = 1; i <= q; i++) ask[i].y = std::lower_bound(c + 1, c + tot + 1, ask[i].y) c; std::sort(p + 1, p + m + 1, cmp1); std::sort(ask + 1, ask + q + 1, cmp2); j = 1; for(i = 1; i <= q; i++) j++; } x = find(ask[i].x); if(ask[i].z > sum[root[x]]) ans[ask[i].id] = 1; else ans[ask[i].id] = b[query(root[x], 1, cnt, sum[root[x]] ask[i].z + 1)]; } for(i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }

　　

上一篇：[BZOJ1578] [Usaco2009 Feb]Stock Market 股票市场（DP）

下一篇：[BZOJ2287]【POJ Challenge】消失之物（DP）

---

线段树 离散化 线段树合并