[luoguP1972] [SDOI2009]HH的项链（莫队 || 树状数组 || 主席树）

传送门

莫队基础题，适合我这种初学者。

莫队是离线算法，通常不带修改，时间复杂度为 O(n√n)

我们要先保证通过 [ l , r ] 求得 [ l , r + 1 ] , [ l , r 1 ] , [ l 1 , r ] , [ l + 1 , r ] 的效率是O(1)的

对于莫队的理解，移步远航休息栈

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 6 int n, m, S, ans = 1; 7 int a[50001], ton[1000001], anslist[200001]; 8 struct node 9 q[200001]; 12 13 inline int read() 14 21 22 inline bool cmp(node x, node y) 23 26 27 int main() 28 47 while(x > q[i].l) 48 53 while(y > q[i].r) 54 59 while(y < q[i].r) 60 65 anslist[q[i].num] = ans; 66 } 67 for(i = 1; i <= m; i++) printf("%d\n", anslist[i]); 68 return 0; 69 }
View Code

代码量真是友善啊

还可以用离线用树状数组来做.

以下是hzwer的解法：

这题首先在线是没法做的，所以我们可以考虑离线算法

首先记录下每种颜色的下一种颜色所在的位置

将所有询问按照左端点进行排序

将所有颜色的第一个点x a[x]++

然后从左往右扫

扫到一个点x将a[next[x]]++

碰到一个询问l,r输出sum[r]sum[l1]

其中sum是a数组的前缀和

求前缀和可以用树状数组

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 const int MAXN = 50001; 7 int n, m, max; 8 int head[MAXN], next[MAXN], a[MAXN], ans[MAXN], c[1000001]; 9 struct node 10 q[MAXN]; 13 14 inline int read() 15 22 23 inline int Max(int x, int y) 24 27 28 inline void update(int x) 29 32 33 inline int query(int x) 34 39 40 inline bool cmp(node x, node y) 41 44 45 int main() 46 62 std::sort(q + 1, q + m + 1, cmp); j = 1; 64 for(i = 1; i <= n; i++) 65 69 for(i = 1; i <= m; i++) printf("%d\n", ans[i]); 70 return 0; 71 }
View Code

主席树也是个好方法。

保存每个点的上一个和它颜色相同的点的位置（如果没有就是0）

然后以每个点的前驱为下标建主席数。

统计时只需要统计当前区间 [x,y] 中前驱小于 x 的点的个数

——代码

1 #include <cstdio> 2 #include <iostream> 3 4 const int MAXN = 50001; 5 int n, m, cnt; 6 int a[MAXN], head[1000001], pre[MAXN], root[MAXN], sum[MAXN * 20], ls[MAXN * 20], rs[MAXN * 20]; 7 8 inline int read() 9 16 17 inline void update(int &now, int l, int r, int x) 18 29 30 inline int query(int x, int y, int l, int r, int k) 31 37 38 int main() 39 48 for(i = 1; i <= n; i++) 49 53 m = read(); 54 for(i = 1; i <= m; i++) 55 60 return 0; 61 }
View Code

上一篇：【转】关于LIS和一类可以用树状数组优化的DP 预备知识

下一篇：[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）

---

主席树 树状数组 模板 莫队