记录编号	397696	评测结果	AAAAAAAAAAA
题目名称	[HEOI 2016] 字符串	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	7.241 s
提交时间	2017-04-20 20:20:49	内存使用	98.82 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <deque>
#include <vector>
const int MAXN = 200020;
const int MAXD = 20;
namespace SAM{
  int next[MAXN][26], link[MAXN], len[MAXN];
  int last = 1, cnt = 1;
  int pos[MAXN>>1];
  void expand(int c, int ps){
    int cur = ++cnt; len[cur] = len[last]+1, pos[ps] = cur;
    int p;
    for(p = last; p && !next[p][c]; p = link[p])next[p][c] = cur;
    if(!p)link[cur] = 1;
    else{
      int q = next[p][c];
      if(len[q] == len[p]+1)link[cur] = q;
      else{
        int clone = ++cnt; len[clone] = len[p]+1, link[clone] = link[q];
        memcpy(next[clone], next[q], sizeof next[0]);
        for(; p && next[p][c] == q; p = link[p])next[p][c] = clone;
        link[cur] = link[q] = clone;
      }
    }
    last = cur;
  }
  int dfs_tim;
  int visit[MAXN], leave[MAXN];
  std::vector<int> G[MAXN];
  void dfs(int u){
    visit[u] = ++dfs_tim;
    for(int i = 0; i < G[u].size(); i++)dfs(G[u][i]);
    leave[u] = dfs_tim;
  }
  int fa[MAXN][MAXD];
  void build_tree(){
    for(int i = 2; i <= cnt; i++)G[link[i]].push_back(i);
    dfs(1);
    for(int i = 2; i <= cnt; i++)
      fa[i][0] = link[i];
    for(int k = 1; 1 << k <= cnt; k++)for(int i = 1; i <= cnt; i++)
      fa[i][k] = fa[fa[i][k-1]][k-1];
  }
}
namespace PST{ //PersistableSegmentTree
  int root[MAXN>>1];
  const int MAXM = 5e6+2;
  int ls[MAXM], rs[MAXM], val[MAXM], cnt;
  int insert(int pre, int p, int L, int R){
    int cur = ++cnt;
    ls[cur] = ls[pre], rs[cur] = rs[pre], val[cur] = val[pre]+1;
    if(L < R){
      int M = (L+R)>>1;
      if(p <= M)ls[cur] = insert(ls[cur], p, L, M);
      else if(p > M)rs[cur] = insert(rs[cur], p, M+1, R);
    }
    return cur;
  }
  int query(int c, int l, int r, int L, int R){
    if(!c)return 0;
    if(l <= L && R <= r)return val[c];
    int M = (L+R)>>1, ret = 0;
    if(l <= M)ret += query(ls[c], l, r, L, M);
    if(r > M)ret += query(rs[c], l, r, M+1, R);
    return ret;
  }  
} 
int n, m;
char str[MAXN>>1];
int a, b, c, d;
int find(int p, int len){
  int t = SAM::pos[p];
  for(int i = MAXD-1; ~i; i--){
    int v = SAM::fa[t][i];
    if(SAM::len[v] >= len)t = v;
  }
  return t;
}
bool check(int len){
  int u = find(c, len);
  int x = PST::query(PST::root[b-len+1], SAM::visit[u], SAM::leave[u], 1, SAM::dfs_tim);
  int y = PST::query(PST::root[a-1], SAM::visit[u], SAM::leave[u], 1, SAM::dfs_tim);
  return x > y;
}
int main(){
  freopen("heoi2016_str.in", "r", stdin); freopen("heoi2016_str.out", "w", stdout);
  scanf("%d %d", &n, &m);
  scanf("%s", str+1);
  for(int i = n; i; i--)SAM::expand(str[i]-'a', i);
  SAM::build_tree();
  for(int i = 1; i <= n; i++)
    PST::root[i] = PST::insert(PST::root[i-1], SAM::visit[SAM::pos[i]], 1, SAM::dfs_tim);
  while(m--){
    scanf("%d %d %d %d", &a, &b, &c, &d);
    int l = 0, r = std::min(b-a+1, d-c+1);
    while(l < r){
      int mid = l+(r-l+1)/2;
      if(check(mid))l = mid; else r = mid-1;
    }
    printf("%d\n", l);
  }
  return 0;
}