[BZOJ3339] Rmq Problem（线段树）

传送门

这个题的方法好像很多啊

1.莫队暴力

2.线段树 + 离线处理

先预处理出sg[i]表示前i个数的sg值，next[i]表示i的下一位置在哪里，如果后面再没有i，那么next[i] = n + 1

然后把线段树的每个叶子节点放上sg[i]。

把询问按照左端点由小到大排序，我们考虑如何从 l ~ r 转移到 l + 1 ~ r，

会发现，当把a[l]这个数去掉之后，如果后面没有a[l]那么答案就可能会更新，

那么我们可以更新 l + 1 ~ next[l] 1这个区间，也就是用线段树操作

#include <cstdio> #include <iostream> #include <algorithm> #define N 200001 #define INF ~(1 << 31) #define root 1, 1, n #define ls now << 1, l, mid #define rs now << 1 | 1, mid + 1, r #define min(x, y) ((x) < (y) ? (x) : (y)) int n, q; int a[N], next[N], vis[N], ans[N], mx[N << 2], sg[N]; struct node p[N]; inline int read() inline bool cmp(node x, node y) inline void build(int now, int l, int r) mx[now] = INF; int mid = (l + r) >> 1; build(ls); build(rs); } inline void push_down(int now) } inline void update(int now, int l, int r, int x, int y, int d) push_down(now); int mid = (l + r) >> 1; if(x <= mid) update(ls, x, y, d); if(mid < y) update(rs, x, y, d); } inline int query(int now, int l, int r, int x) int main() build(root); for(i = 0; i <= n; i++) vis[i] = n + 1; for(i = n; i >= 1; i) next[i] = vis[a[i]], vis[a[i]] = i; for(i = 1; i <= q; i++) std::sort(p + 1, p + q + 1, cmp); for(i = 1; i <= q; i++) ans[p[i].id] = query(root, p[i].y); } for(i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }

3.主席树

。。不会

上一篇：[BZOJ4756] [Usaco2017 Jan]Promotion Counting（线段树合并）

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

---

主席树 线段树 莫队