题解
我们冷静一下，先画一棵后缀树
然后发现我们要给c和d这一段区间在[a,b]这一段开头的串里找lcp
而lcp呢，就是c点的祖先的到根的一段，假如这个祖先的子树里有[a,b - dis[u] + 1]，那么这个u就是合法的，维护每个点子树里出现过的后缀串起点可以用线段树合并
(这里的深度指后缀树上该点到根的距离）
我们先用min(b - a + 1,c - d + 1)限制一下这个祖先的深度，选择距离根深度最近且深度>= min(b - a + 1,c - d + 1)，找的这个点称为p
那么我们要找最长的合法的部分，可以二分，二分的log，倍增找点的log，线段树里判断是否合法的log，一共是三个log，当然，我们冷静一下，显然有些log常数非常小嘛
但是我们再冷静一下，我们可以发现，我们要找的点可以当做c的祖先中，深度最小的，且子树中不存在[a,b - dis[u] + 1]的点u，我们可以从高位到低位枚举二进制位，按位判断让p跳还是不跳，这就是两个log了
同时这个高位到低位枚举二进制位也可用于找到p
那么这个时候难道p的父亲的深度就是答案了吗？too naive
是p的深度到p的父亲的深度都可能，我们需要再次二分，二分的左边界p的父亲的深度，右边界是min(p的深度 - 1,min(b - a + 1,d - c + 1))
复杂度最后还是\(O(n \log^2 n)\)
代码
#include <bits/stdc++.h>
#define enter putchar('\n')
#define space putchar(' ')
#define pii pair<int,int>
#define fi first
#define se second
#define MAXN 200005
#define pb push_back
#define mp make_pair
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M;
char s[MAXN];
int id[MAXN];
struct node {
int to,next,val;
}E[MAXN * 4];
int head[MAXN],sumE,Ncnt,fa[MAXN][20],dis[MAXN],pos[MAXN];
void add(int u,int v,int c) {E[++sumE].to = v;E[sumE].next = head[u];E[sumE].val = c;head[u] = sumE;}
namespace SAM {
struct node {
node *nxt[26],*par;
int len,cnt;
}pool[MAXN * 2],*tail = pool,*root,*last,*que[MAXN * 2];
int c[MAXN];
void Init() {
root = last = tail++;
}
void build_sam(int l,int c) {
node *nowp = tail++,*p;
nowp->len = l;nowp->cnt = 1;
for(p = last ; p && !p->nxt[c]; p = p->par) {
p->nxt[c] = nowp;
}
if(!p) nowp->par = root;
else {
node *q = p->nxt[c];
if(q->len == p->len + 1) nowp->par = q;
else {
node *copyq = tail++;
*copyq = *q;
copyq->len = p->len + 1;copyq->cnt = 0;
q->par = nowp->par = copyq;
for(; p && p->nxt[c] == q ; p = p->par) {
p->nxt[c] = copyq;
}
}
}
last = nowp;
}
void build_suffix_tree() {
Ncnt = tail - pool;
for(int i = 0 ; i < Ncnt ; ++i) {
c[pool[i].len]++;
}
for(int i = 1 ; i <= N ; ++i) c[i] += c[i - 1];
for(int i = 0 ; i < Ncnt ; ++i) {
que[c[pool[i].len]--] = &pool[i];
}
for(int i = 1 ; i <= Ncnt ; ++i) {
int u = que[i] - pool + 1;
if(que[i]->par) {
int f = que[i]->par - pool + 1;
fa[u][0] = f;
add(f,u,que[i]->len - que[i]->par->len);
add(u,f,que[i]->len - que[i]->par->len);
}
if(que[i]->cnt) {id[N - que[i]->len + 1] = u;pos[u] = N - que[i]->len + 1;}
}
}
}
namespace seg_tr {
struct node {
int lc,rc;
}tr[MAXN * 80];
int rt[MAXN],Ncnt;
void Insert(int x,int &u,int L,int R,int pos) {
u = ++Ncnt;
tr[u] = tr[x];
if(L == R) return;
int mid = (L + R) >> 1;
if(pos <= mid) Insert(tr[x].lc,tr[u].lc,L,mid,pos);
else Insert(tr[x].rc,tr[u].rc,mid + 1,R,pos);
}
int Merge(int Lt,int Rt) {
if(!Lt) return Rt;
if(!Rt) return Lt;
int u = ++Ncnt;
tr[u].lc = Merge(tr[Lt].lc,tr[Rt].lc);
tr[u].rc = Merge(tr[Lt].rc,tr[Rt].rc);
return u;
}
bool Query(int u,int L,int R,int l,int r) {
if(!u) return false;
if(L == l && R == r) return 1;
int mid = (L + R) >> 1;
if(r <= mid) return Query(tr[u].lc,L,mid,l,r);
else if(l > mid) return Query(tr[u].rc,mid + 1,R,l,r);
else return Query(tr[u].lc,L,mid,l,mid) || Query(tr[u].rc,mid + 1,R,mid + 1,r);
}
}
using seg_tr::rt;
using seg_tr::Merge;
using seg_tr::Insert;
using seg_tr::Query;
void dfs(int u) {
if(pos[u]) {Insert(rt[u],rt[u],1,N,pos[u]);}
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u][0]) {
dis[v] = dis[u] + E[i].val;
dfs(v);
rt[u] = Merge(rt[u],rt[v]);
}
}
}
void Init() {
read(N);read(M);
scanf("%s",s + 1);
reverse(s + 1,s + N + 1);
SAM::Init();
for(int i = 1 ; i <= N ; ++i) {
SAM::build_sam(i,s[i] - 'a');
}
SAM::build_suffix_tree();
dfs(1);
for(int j = 1 ; j <= 17 ; ++j) {
for(int i = 1 ; i <= Ncnt ; ++i) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
}
void Solve() {
int a,b,c,d;
for(int i = 1 ; i <= M ; ++i) {
read(a);read(b);read(c);read(d);
int l = min(d - c + 1,b - a + 1);
int p = id[c];
for(int j = 17 ; j >= 0 ; --j) {
if(!fa[p][j]) continue;
if(dis[fa[p][j]] >= l) p = fa[p][j];
}
if(Query(rt[p],1,N,a,b - min(dis[p],l) + 1)) {
out(min(dis[p],l));enter;continue;
}
for(int j = 17 ; j >= 0 ; --j) {
if(!fa[p][j]) continue;
int u = fa[p][j];
if(!Query(rt[u],1,N,a,b - dis[u] + 1)) p = fa[p][j];
}
if(dis[p] == dis[fa[p][0]] + 1 || dis[fa[p][0]] >= l) {
p = fa[p][0];
out(min(dis[p],l));enter;
}
else {
int L = dis[fa[p][0]],R = min(dis[p] - 1,l);
while(L < R) {
int mid = (L + R + 1) >> 1;
if(Query(rt[p],1,N,a,b - mid + 1)) L = mid;
else R = mid - 1;
}
out(L);enter;
}
}
}
int main() {
Init();
Solve();
return 0;
}
我的代码能力真是低到要哭了！
真的哭了！
写跪了三次啊，debug到吐啊。。。