[BZOJ3932] [CQOI2015]任务查询系统（主席树 || 树状数组 套 主席树 + 差分 + 离散化）

传送门

看到这个题有个很暴力的想法，

可以每一个时间点都建一颗主席树，主席树上叶子节点 i 表示优先级为 i 的任务有多少个。

当 x 到 y 有个优先级为 k 的任务时，循环 x 到 y 的每个点，都插入一个 k。

当然这样肯定完蛋。

x 到 y 插入一个优先级为 k 的任务？

想到差分，给时间点为 x 的主席树插入 k，给时间点为 y + 1 的主席树插入 k。

那么求一个树状数组的前缀和就好了。

前缀和？

用树状数组优化。

这样就可以用 树状数组 套 主席树 来做。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define LL long long 5 6 const int MAXN = 1e5 + 5, p = 200; 7 int n, m, cnt, t; 8 int S[MAXN], E[MAXN], P[MAXN], num[MAXN], root[MAXN], id[MAXN], q[21], s[MAXN * p], ls[MAXN * p], rs[MAXN * p]; 9 LL sum[MAXN * p], pre = 1; 10 11 inline int read() 12 19 20 inline bool cmp(int x, int y) 21 24 25 inline void insert(int last, int &now, int l, int r, int x, int v1, int v2) 26 34 35 inline LL query(int l, int r, int k) 36 43 LL t2 = 0; 44 int t1 = 0, mid = (l + r) >> 1; 45 for(int i = 1; i <= t; i++) t1 += s[ls[q[i]]], t2 += sum[ls[q[i]]]; 46 if(k <= t1) 47 51 else 52 56 } 57 58 int main() 59 71 std::sort(id + 1, id + n + 1, cmp); 72 for(i = 1; i <= n; i++) num[id[i]] = i; 73 for(i = 1; i <= n; i++) 74 78 for(i = 1; i <= m; i++) 79 87 return 0; 88 }
View Code

其实如果按照时间排序的话，依次插入主席树，就可以维护前缀和，而省去了树状数组的麻烦。

然后注意的是每个时间点有可能会有多颗主席树。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define LL long long 5 6 const int MAXN = 1e5 + 5; 7 int n, m, tot, size, cnt; 8 int num[MAXN], id[MAXN], v[MAXN], ls[MAXN * 40], rs[MAXN * 40], s[MAXN * 40], root[MAXN]; 9 LL pre = 1, sum[MAXN * 40]; 10 struct node 11 p[MAXN * 2]; 14 15 inline int read() 16 23 24 inline bool cmp(node x, node y) 25 28 29 inline void insert(int &now, int l, int r, int x, int v1, int v2) 30 42 43 inline LL query(int now, int l, int r, int x) 44 50 51 inline bool cmp1(int x, int y) 52 55 56 int main() 57 71 std::sort(num + 1, num + n + 1, cmp1); 72 for(i = 1; i <= n; i++) id[num[i]] = i; 73 /*std::sort(v + 1, v + n + 1); 74 size = std::unique(v + 1, v + n + 1) (v + 1); 75 for(i = 1; i <= n; i++) id[i] = std::lower_bound(v + 1, v + size + 1, id[i]) v;*/ 76 tot = 0; 77 for(i = 1; i <= n; i++) p[++tot].num = id[i], p[++tot].num = id[i]; 78 std::sort(p + 1, p + tot + 1, cmp); 79 j = 1; 80 for(i = 1; i <= m; i++) 81 86 for(i = 1; i <= m; i++) 87 95 return 0; 96 }
View Code

最后，需要注意对动态开点的理解。

以及，这个题是对优先级离散化，优先级有可能有相同的，但是离散化却不去重，这就会使得相同数值会是递增的一段数。

为什么不去重？

这是为了方便找前 k 个。

如果去重，有可能 query 时，找到一个叶子节点它的个数会超过一个，比如说 5 个，而只要找 3 个，那样处理就比较麻烦，还得再记录每个叶子节点的优先级。

不去重就保证了每个叶节点的个数只有一个，而对于答案没有影响。

上一篇：[luoguP1351] 联合权值（Dfs）

下一篇：[luoguP2038] 无线网络发射器选址（模拟）

---

stl 主席树 树状数组 差分 离散化 树套树