经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
BZOJ4516: [Sdoi2016]生成魔咒(后缀数组 set RMQ)
来源:cnblogs  作者:自为风月马前卒  时间:2018/11/29 9:27:48  对本文有异议

题意

题目链接

Sol

毒瘤SDOI 终于有一道我会做的题啦qwq

首先,本质不同的子串的个数 $ = \frac{n(n + 1)}{2} - \sum height[i]$

把原串翻转过来,每次就相当于添加一个后缀

然后直接用set xjb维护一下前驱后继就行了

时间复杂度:\(O(nlogn)\)

  1. // luogu-judger-enable-o2
  2. // luogu-judger-enable-o2
  3. #include<bits/stdc++.h>
  4. #define sit set<int>::iterator
  5. #define LL long long
  6. using namespace std;
  7. const int MAXN = 2e5 + 10;
  8. const int INF = 2333;
  9. inline int read() {
  10. char c = getchar(); int x = 0, f = 1;
  11. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  12. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  13. return x * f;
  14. }
  15. int N, M, L, rak[MAXN], tax[MAXN], tp[MAXN], sa[MAXN], H[MAXN], f[MAXN][20], lg2[MAXN], s[MAXN], date[MAXN], ans[MAXN];
  16. set<int> st;
  17. void Qsort() {
  18. for(int i = 0; i <= M; i++) tax[i] = 0;
  19. for(int i = 1; i <= N; i++) tax[rak[i]]++;
  20. for(int i = 1; i <= M; i++) tax[i] += tax[i - 1];
  21. for(int i = N; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
  22. }
  23. void SuffixSort() {
  24. for(int i = 1; i <= N; i++) rak[i] = s[i], tp[i] = i; M = 233; Qsort();
  25. for(int w = 1, p = 0; p < N; w <<= 1, M = p) { p = 0;
  26. for(int i = 1; i <= w; i++) tp[++p] = N - i + 1;
  27. for(int i = 1; i <= N; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
  28. Qsort(); swap(tp, rak); rak[sa[1]] = p = 1;
  29. for(int i = 2; i <= N; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;
  30. }
  31. for(int i = 1, k = 0; i <= N; i++) {
  32. if(k) k--; int j = sa[rak[i] - 1];
  33. while(s[i + k] == s[j + k]) k++;
  34. H[rak[i]] = k;
  35. }
  36. }
  37. void Pre() {
  38. for(int i = 1; i <= N; i++) f[i][0] = H[i];
  39. for(int j = 1; j <= 17; j++)
  40. for(int i = 1; i + (1 << j) - 1 <= N; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
  41. }
  42. int Query(int x, int y) {
  43. if(x > y) swap(x, y); x++;
  44. int k = lg2[y - x + 1];
  45. return min(f[x][k], f[y - (1 << k) + 1][k]);
  46. }
  47. void Des() {
  48. sort(date + 1, date + N + 1);
  49. int num = unique(date + 1, date + N + 1) - date - 1;
  50. for(int i = 1; i <= N; i++) s[i] = lower_bound(date + 1, date + num + 1, s[i]) - date;
  51. reverse(s + 1, s + N + 1);
  52. }
  53. int main() {
  54. lg2[1] = 0; for(int i = 2; i <= MAXN - 1; i++) lg2[i] = lg2[i >> 1] + 1;
  55. N = read();
  56. for(int i = 1; i <= N; i++) s[i] = date[i] = read();
  57. Des();
  58. SuffixSort(); Pre();
  59. st.insert(0); st.insert(N + 1);
  60. LL now = 0; st.insert(rak[N]); ans[N] = 1;
  61. printf("%lld\n", 1);
  62. for(int i = N - 1; i >= 1; i--) {
  63. sit nxt = st.upper_bound(rak[i]), pre;
  64. if(*nxt == 0) pre = st.begin();
  65. else pre = --nxt, nxt++;
  66. // printf("%d %d\n", *pre, *nxt);
  67. if(*pre != 0 && *nxt != N + 1) now -= Query(*pre, *nxt);
  68. if(*pre != 0 && *pre != N + 1) now += Query(*pre, rak[i]);
  69. if(*nxt != 0 && *nxt != N + 1) now += Query(rak[i], *nxt);
  70. printf("%lld\n", 1ll * (N - i + 1) * ((N - i + 1) + 1) / 2 - now);
  71. st.insert(rak[i]);
  72. }
  73. return 0;
  74. }
  75. /*
  76. 4
  77. 1 2 3 3
  78. 3
  79. 1 3 1
  80. */
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号