BZOJ4516: [Sdoi2016]生成魔咒(后缀数组 set RMQ)

题意

题目链接

Sol

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

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

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

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

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

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define sit set<int>::iterator
#define LL long long 
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 2333;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
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];
set<int> st;
void Qsort() {
    for(int i = 0; i <= M; i++) tax[i] = 0;
    for(int i = 1; i <= N; i++) tax[rak[i]]++;
    for(int i = 1; i <= M; i++) tax[i] += tax[i - 1];
    for(int i = N; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
void SuffixSort() {
    for(int i = 1; i <= N; i++) rak[i] = s[i], tp[i] = i; M = 233; Qsort();
    for(int w = 1, p = 0; p < N; w <<= 1, M = p) { p = 0;
        for(int i = 1; i <= w; i++) tp[++p] = N - i + 1;
        for(int i = 1; i <= N; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
        Qsort(); swap(tp, rak); rak[sa[1]] = p = 1;
        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;
    }
    for(int i = 1, k = 0; i <= N; i++) {
        if(k) k--; int j = sa[rak[i] - 1];
        while(s[i + k] == s[j + k]) k++;
        H[rak[i]] = k;
    } 
}
void Pre() {
    for(int i = 1; i <= N; i++) f[i][0] = H[i];
    for(int j = 1; j <= 17; j++)
        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]);
}
int Query(int x, int y) {
    if(x > y) swap(x, y); x++;
    int k = lg2[y - x + 1];
    return min(f[x][k], f[y - (1 << k) + 1][k]);
}
void Des() {
    sort(date + 1, date + N + 1);
    int num = unique(date + 1, date + N + 1) - date - 1;
    for(int i = 1; i <= N; i++) s[i] = lower_bound(date + 1, date + num + 1, s[i]) - date;
    reverse(s + 1, s + N + 1);
}
int main() {
    lg2[1] = 0; for(int i = 2; i <= MAXN - 1; i++) lg2[i] = lg2[i >> 1] + 1;
    N = read();
    for(int i = 1; i <= N; i++) s[i] = date[i] = read();
    Des();  
    SuffixSort(); Pre();
    st.insert(0); st.insert(N + 1);
    LL now = 0; st.insert(rak[N]); ans[N] = 1;
    printf("%lld\n", 1);
    for(int i = N - 1; i >= 1; i--) {
        sit nxt = st.upper_bound(rak[i]), pre;
        if(*nxt == 0) pre = st.begin();
        else pre = --nxt, nxt++;
    //  printf("%d %d\n", *pre, *nxt);
        if(*pre != 0 && *nxt != N + 1) now -= Query(*pre, *nxt);
        if(*pre != 0 && *pre != N + 1) now += Query(*pre, rak[i]);
        if(*nxt != 0 && *nxt != N + 1) now += Query(rak[i], *nxt);
        printf("%lld\n", 1ll * (N - i + 1) * ((N - i + 1) + 1) / 2 - now);
        st.insert(rak[i]);
    }
    return 0;
}
/*
4
1 2 3 3

3
1 3 1
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JMCui

再学习之MyBatis.

一、框架基本介绍 1、概念 支持普通SQL查询、存储过程和高级映射,简化和实现了Java 数据持久化层的的开源框架,主要流行的原因在于他的简单性和易使用性。 2...

49880
来自专栏Samego技术资源分享

数据库Dao层抽象出BasicDao类 | 许久没碰Java了、致Java初学者

19240
来自专栏我是攻城师

ElasticSearch的Mapping之字段类型

33950
来自专栏听雨堂

Python防止sql注入

看了网上文章,说的都挺好的,给cursor.execute传递格式串和参数,就能防止注入,但是我写了代码,却死活跑不通,怀疑自己用了一个假的python 最后,...

42270
来自专栏Java3y

纳税服务系统六(信息发布管理模块)【Ueditor、异步信息交互、抽取BaseService、条件查询、分页】

需求分析 我们现在来到了纳税服务系统的信息发布管理模块,首先我们跟着原型图来进行需求分析把: 一些普通的CRUD,值得一做的就是状态之间的切换了。停用和发布切换...

52860
来自专栏跟着阿笨一起玩NET

C#常用操作类库四(File操作类)

30110
来自专栏Hongten

spring开发_Spring+Struts2

http://www.cnblogs.com/hongten/gallery/image/112920.html

10920
来自专栏芋道源码1024

数据库中间件 MyCAT 源码解析 —— 分片结果合并(一)

1. 概述 相信很多同学看过 MySQL 各种优化的文章,里面 99% 会提到:单表数据量大了,需要进行分片(水平拆分 or 垂直拆分)。分片之后,业务上必然面...

480130
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常——存储过程知识普及

存储过程是保存可以接受或返回用户提供参数的SQL语句集合。在日常的使用中,经常会遇到复杂的业务逻辑和对数据库的操作,使用存储过程可以进行封装。可以在数据库中定...

20180
来自专栏Pythonista

Django进阶知识

django为使用一种新的方式,即:关系对象映射(Object Relational Mapping,简称ORM)。

31620

扫码关注云+社区

领取腾讯云代金券