| 记录编号 |
266885 |
评测结果 |
EEEEEEEEEEE |
| 题目名称 |
[HEOI 2016] 字符串 |
最终得分 |
0 |
| 用户昵称 |
 Aglove |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.814 s |
| 提交时间 |
2016-06-10 06:38:40 |
内存使用 |
101.98 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=200010;
int n,m,tot,la;
int a,b,c,d;
char s[maxn];
int p[maxn];
struct Node{
int next[26];
int len,link;
}st[maxn];
int h[maxn],cnt=0;
struct edge{
int to,next;
}G[maxn<<1];
int anc[maxn][20],dep[maxn];
int pos[maxn],end[maxn],sum=0;
int rt[maxn];
struct Seg_Tree{
int L,R,v;
}t[5000010];
void add(int x,int y){
++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void init(){
tot=la=0;
st[0].link=-1;
}
int insert(int c){
int cur=++tot;
st[cur].len=st[la].len+1;
int p;
for(p=la;p!=-1&&st[p].next[c]==0;p=st[p].link)st[p].next[c]=cur;
if(p==-1)st[cur].link=0;
else{
int q=st[p].next[c];
if(st[q].len==st[p].len+1)st[cur].link=q;
else{
int clone=++tot;
st[clone]=st[q];
st[clone].len=st[p].len+1;
for(;p!=-1&&st[p].next[c]==q;p=st[p].link)st[p].next[c]=clone;
st[q].link=st[cur].link=clone;
}
}la=cur;return la;
}
void DFS(int u,int f){
anc[u][0]=f;pos[u]=++sum;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(v==f)continue;
dep[v]=dep[u]+1;
//printf("%d %d\n",u,v);
DFS(v,u);
}end[u]=sum;
}
void pre_LCA(){
for(int i=0;i<=tot;++i){
for(int j=1;(1<<j)<=tot;++j)anc[i][j]=-1;
}
for(int j=1;(1<<j)<=tot;++j){
for(int i=1;i<=tot;++i){
if(anc[i][j-1]!=-1){
int a=anc[i][j-1];
anc[i][j]=anc[a][j-1];
}
}
}return;
}
void build(int &o,int L,int R){
o=++cnt;
if(L==R)return;
int mid=(L+R)>>1;
build(t[o].L,L,mid);
build(t[o].R,mid+1,R);
}
void UPD(int &o,int L,int R,int p){
t[++cnt]=t[o];o=cnt;
if(L==R){t[o].v++;return;}
int mid=(L+R)>>1;
if(p<=mid)UPD(t[o].L,L,mid,p);
else UPD(t[o].R,mid+1,R,p);
t[o].v=t[t[o].L].v+t[t[o].R].v;
}
int ask(int o,int L,int R,int x,int y){
if(L>=x&&R<=y)return t[o].v;
int mid=(L+R)>>1;
if(y<=mid)return ask(t[o].L,L,mid,x,y);
else if(x>mid)return ask(t[o].R,mid+1,R,x,y);
else return ask(t[o].L,L,mid,x,y)+ask(t[o].R,mid+1,R,x,y);
}
int find(int p){
int log;
for(log=0;(1<<log)<=dep[p];++log);--log;
for(int i=log;i>=0;--i){
if(anc[p][i]!=-1&&st[anc[p][i]].len>=d-c+1){
p=anc[p][i];
}
}return p;
}
int Get_pos(int p,int k){
int log;
for(log=0;(1<<log)<=dep[p];++log);--log;
for(int i=log;i>=0;--i){
if(anc[p][i]!=-1&&dep[anc[p][i]]>=k)p=anc[p][i];
}return p;
}
bool check(int u){
int L,B,A;
if(st[u].link==-1)L=0;
else L=st[st[u].link].len+1;
if(b-a+1<L)return false;
B=ask(rt[b-L+1],1,sum,pos[u],end[u]);
A=ask(rt[a-1],1,sum,pos[u],end[u]);
if(B-A>0)return true;
else return false;
}
bool judge(int u,int L){
int A,B;
if(b-a+1<L)return false;
B=ask(rt[b-L+1],1,sum,pos[u],end[u]);
A=ask(rt[a-1],1,sum,pos[u],end[u]);
if(B-A>0)return true;
else return false;
}
void debug(){
for(int i=0;i<=tot;++i){
for(int j=0;j<26;++j){
if(st[i].next[j]){
printf("%d -> %d %c\n",i,st[i].next[j],j+'a');
}
}
}printf("\n");
}
void Get_s(){
int len=0;
char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='a'&&ch<='z')s[++len]=ch,ch=getchar();
}
int main(){
freopen("heoi2016_str.in","r",stdin);
freopen("heoi2016_str.out","w",stdout);
int __size__=32<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));
read(n);read(m);init();
Get_s();
for(int i=n;i>=1;--i)p[i]=insert(s[i]-'a');
for(int i=1;i<=tot;++i)add(st[i].link,i);
DFS(0,-1);cnt=0;build(rt[0],1,sum);
for(int i=1;i<=n;++i){
rt[i]=rt[i-1];
UPD(rt[i],1,sum,pos[p[i]]);
}pre_LCA();
while(m--){
read(a);read(b);read(c);read(d);
int u=find(p[c]);
int L=0,R=dep[u];
while(L<R){
int mid=L+((R-L+1)>>1);
int v=Get_pos(u,mid);
if(check(v))L=mid;
else R=mid-1;
}
u=Get_pos(u,L);
int A,B;
if(st[u].link==-1)A=0;
else A=st[st[u].link].len+1;
B=st[u].len;
while(A<B){
int mid=A+((B-A+1)>>1);
if(judge(u,mid))A=mid;
else B=mid-1;
}A=min(A,d-c+1);
printf("%d\n",A);
}return 0;
}