P2463 [SDOI2008]Sandy的卡片

套路都差不多,都是差分后二分答案找lcp。只是这题要把多个串拼接起来成为一个大串,中间用某些值域中没有的数字相隔(最好间隔符都不一样想想为什么),排序后在二分答案,开个栈统计即可(保证单次check复杂度O(N))。

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;//m<=101不是m<=100大小没算好坑死我了
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
inline int read(){
int f=,x=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return f?-x:x;
}
int a[N],pos[N],bin[N],vis[N],tot;
int n,l,x,ans,tmp,mid,L,R=; int sa[N],h[N],cnt[N],y[N],rk[N],p,m;
inline void suffix_sort(){m=;
for(register int i=;i<=tot;++i)++cnt[rk[i]=a[i]];
for(register int i=;i<=m;++i)cnt[i]+=cnt[i-];
for(register int i=tot;i;--i)sa[cnt[rk[i]]--]=i;
for(register int k=;k<tot;k<<=,p=){
for(register int i=tot-k+;i<=tot;++i)y[++p]=i;
for(register int i=;i<=tot;++i)if(sa[i]>k)y[++p]=sa[i]-k;
for(register int i=;i<=m;++i)cnt[i]=;
for(register int i=;i<=tot;++i)++cnt[rk[y[i]]];
for(register int i=;i<=m;++i)cnt[i]+=cnt[i-];
for(register int i=tot;i;--i)sa[cnt[rk[y[i]]]--]=y[i];
swap(rk,y);rk[sa[]]=p=;
for(register int i=;i<=tot;++i)rk[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p:++p;
if(p==tot)break;m=p;
}p=;
for(register int i=;i<=tot;h[rk[i]]=p,p?--p:,++i)while(a[i+p]==a[sa[rk[i]-]+p]&&++p);
} inline int check(int k){
for(register int i=;a[sa[i]]<=;++i){
if(h[i]<k){while(x)vis[bin[x--]]=;}
if(!vis[pos[sa[i]]])vis[pos[sa[i]]]=,bin[++x]=pos[sa[i]];
if(x==n)return ;
}
return ;
} int main(){//freopen("tmp.in","r",stdin);
n=read();
for(register int i=;i<=n;++i){
l=read();a[++tot]=read();pos[tot]=i;
for(register int j=;j<=l;++j)a[++tot]=read(),a[tot-]=a[tot]-a[tot-]+,pos[tot]=i;
a[tot]=i+;
}
suffix_sort();
while(L<=R){
mid=L+R>>;
if(check(mid))ans=mid,L=mid+;
else R=mid-;
}
printf("%d\n",ans+);
return ;
}

最新文章

  1. 让Visual Studio 2013为你自动生成XML反序列化的类
  2. angular 页面加载时可以调用 函数处理
  3. Codeforces Round #261 (Div. 2) D. Pashmak and Parmida&#39;s problem (树状数组求逆序数 变形)
  4. ecshop收货人信息中修改手机号为必填
  5. (传智博客)tp开发第一天之tp执行流程分析笔记
  6. 优先级和lisp式前缀表达式
  7. mysql编码和Java编码相应一览表
  8. ILMerge 简单使用
  9. mysql shutdown and kill
  10. CodeSmith系列(三)——使用CodeSmith生成ASP.NET页面
  11. 0e开头MD5值小结
  12. 题解:[GXOI/GZOI2019]与或和
  13. 卡特兰数 Catalan 笔记
  14. vb 导出excel生成图表统计
  15. 利用Hibernate子查询(in) 得到部分字段(实体类的构造函数)
  16. Centos7.4下安装Nginx
  17. 【CF375C】Circling Round Treasures
  18. Django 前后台的数据传递示列
  19. Robot Framework(用户关键字)
  20. 关于在webapi + ef + 视图 + top查询的问题

热门文章

  1. Orcad CIS怎么批量修改字体大小
  2. FTP 连接报错
  3. Spring Boot从入门到实战:整合Web项目常用功能
  4. git是一种分布式代码管理工具,git通过树的形式记录文件的更改历史,比如: base&#39;&lt;--base&lt;--A&lt;--A&#39; ^ | --- B&lt;--B&#39; 小米工程师常常需要寻找两个分支最近的分割点,即base.假设git 树是多叉树,请实现一个算法,计算git树上任意两点的最近分割点。 (假设git树节点数为n,用邻接矩阵的形式表示git树:字符串数组matrix包含n个字符串,每个字符串由字符&#39;0
  5. 查看SELinux状态并关闭SELinux
  6. 统计分析表的存储过程遇ORA-00600错误分析与处理
  7. android菜鸟学习笔记12----Android控件(一) 几个常用的简单控件
  8. ABAP 性能优化001
  9. web项目中从不同的路径读取文件
  10. Node.js学习笔记(2):基本模块