bzoj3879
2024-10-10 07:57:52
题解:
后缀数组
然后把读入的内容去重,按照rank排序
然后用单调栈处理一下
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
const ll M=23333333333333333ll;
int r[N],ra[N],rb[N],a,st[N],h[N],sa[N],rank[N],n,m,Q;
int q[N],t,ls[N],rs[N],f[N][],Log[N],vis[N],v[N],s[N];
ll ans;
char str[N];
void build()
{
int *x=ra,*y=rb;
for (int i=;i<n;i++)st[x[i]=r[i]]++;
for (int i=;i<m;i++)st[i]+=st[i-];
for (int i=n-;i>=;i--) sa[--st[x[i]]]=i;
for (int j=,p=;p<n;j<<=,m=p)
{
p=;
for (int i=n-j;i<n;i++)y[p++]=i;
for (int i=;i<n;i++)
if (sa[i]>=j)y[p++]=sa[i]-j;
for (int i=;i<m;i++)st[i]=;
for (int i=;i<n;i++)st[x[y[i]]]++;
for (int i=;i<m;i++)st[i]+=st[i-];
for (int i=n-;i>=;i--)sa[--st[x[y[i]]]]=y[i];
swap(x,y);x[sa[]]=;
for (int i=p=;i<n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+j]==y[sa[i-]+j])?p-:p++;
}
for (int i=;i<n;i++)rank[sa[i]]=i;
for (int i=,k=;i<n-;h[rank[i++]]=k)
{
if (k)k--;
for (int j=sa[rank[i]-];r[i+k]==r[j+k];k++);
}
}
int cmp(int a,int b){return rank[a]<rank[b];}
int query(int a,int b)
{
int k=Log[b-a+];
return min(f[a][k],f[b-(<<k)+][k]);
}
int main()
{
scanf("%d%d%s",&n,&Q,str);
for (int i=;i<n;i++)r[i]=str[i]-'a'+;
n++;m=;build();n--;
for (int i=;i<=n;i++)f[i][]=h[i];
for (int j=;(<<j)<n;j++)
for (int i=;i+(<<j)-<=n;i++)f[i][j]=min(f[i][j-],f[i+(<<j-)][j-]);
for (int i=;i<=n;i++)Log[i]=Log[i>>]+;
while (Q--)
{
scanf("%d",&a);
for (int j=;j<=a;j++)
{
scanf("%d",&v[j]);
v[j]--;
if (vis[v[j]])j--,a--;
vis[v[j]]=;
}
sort(v+,v+a+,cmp);
for (int j=;j<a;j++)s[j]=query(rank[v[j]]+,rank[v[j+]]);
s[]=s[a]=-;q[]=;t=;
for (int j=;j<a;j++)
{
while (t&&s[q[t]]>s[j])t--;
ls[j]=q[t],q[++t]=j;
}
t=,q[]=a;
for (int j=a-;j>;j--)
{
while (t&&s[q[t]]>=s[j])t--;
rs[j]=q[t],q[++t]=j;
}
ans=;
for (int j=;j<a;j++)ans=(ans+(ll)(j-ls[j])*(rs[j]-j)*s[j])%M;
printf("%lld\n",ans);
for (int j=;j<=a;j++)vis[v[j]]=;
}
}
最新文章
- HDU3038 How Many Answers Are Wrong[带权并查集]
- mantis邮箱配置
- Website Speed Optimization Guide for Google PageSpeed Rules
- IOS model的getter和setter方法
- 一些git命令
- MySQL 数据表修复及数据恢复
- Unity编译Android的原理解析和apk打包分析
- vue2 vue-router 组装
- Google 搜索引擎语法
- request.getContextPath()
- ArcGis使用字段别名Alias Name导出Excel
- How to avoid the 0-byte file on Webclient download error
- B树、B-树、B+树、B*树相关
- 谁记录了mysql error log中的超长信息(记pt-stalk一个bug的定位过程)
- Linux中使用sed命令或awk命令修改常规配置文件
- HDU 1016 S-Nim ----SG求值
- javascript this(上)
- python程序练习题集
- Tomcat集群的session共享
- office2016破解激活安装
热门文章
- 《剑指offer》第四十四题(数字序列中某一位的数字)
- 学习笔记39—笑谈FireFox标签不同步(IOS和Wiindows)
- (转载)Attempting to add QLayout ";"; to MainWindow ";";, which already has a layout
- CSS段落对齐方式
- tomcat去除项目名部署
- input = time 微信端(移动端)
- python中的静态方法、类方法、属性方法(福利:关于几种方法更好的解释)
- WCF服务寄宿IIS与Windows服务 - C#/.NET
- 进程状态TASK_UNINTERRUPTIBLE
- js新打开页面