bzoj4556 [Tjoi2016&Heoi2016]字符串 可持久化线段树+后缀数组+二分

#Description

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了

一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CE

O，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a…b]的所有子串和s[c…d]的最长公

共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来

m行，每行有4个数a,b,c,d，表示询问s[a…b]的所有子串和s[c…d]的最长公共前缀的最大值。1<=n,m<=100,000,

字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n

#Solution

注意到一个串是固定的，他们的LCP等价于首字母代表后缀的LCP，也就是rank相邻的一段height的最小值

我们二分答案，那么对于c而言合法区间一定是连续的一段。我们二分出合法区间的左右端点后就变成判定性问题，即[a,b]这一段与合法区间是否存在交集，这个可以主席树

然后就做完了，非常的码农

其实可以二分哈希暴力排序，反正复杂度都是两个log的

#Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))
#define copy(x,t) memcpy(x,t,sizeof(x))

const int N=200005;

struct treeNode {
	int l,r,sum;
} t[N*44];

int min[N][18],llgg[N];
int rank[N],sa[N],h[N];
int b[N],c[N],d[N];
int root[N],tot,n;

char s[N];

void get_sa(int n) {
	rep(i,0,'z') b[i]=0;
	rep(i,1,n) b[(int)s[i]]++;
	rep(i,1,'z') b[i]+=b[i-1];
	drp(i,n,1) c[b[(int)s[i]]--]=i;
	int t=0;
	rep(i,1,n) {
		if (s[c[i]]!=s[c[i-1]]) t++;
		rank[c[i]]=t;
	}
	for (int j=1;j<=n;j<<=1) {
		rep(i,0,n) b[i]=0;
		rep(i,1,n) b[rank[i+j]]++;
		rep(i,1,n) b[i]+=b[i-1];
		drp(i,n,1) c[b[rank[i+j]]--]=i;
		rep(i,0,n) b[i]=0;
		rep(i,1,n) b[rank[i]]++;
		rep(i,1,n) b[i]+=b[i-1];
		drp(i,n,1) d[b[rank[c[i]]]--]=c[i];
		int t=0;
		rep(i,1,n) {
			if ((rank[d[i]]!=rank[d[i-1]])||(rank[d[i]]==rank[d[i-1]])&&(rank[d[i]+j]!=rank[d[i-1]+j])) t++;
			c[d[i]]=t;
		}
		rep(i,1,n) rank[i]=c[i];
		if (t==n) break;
	}
	rep(i,1,n) sa[rank[i]]=i;
}

void get_height(int n) {
	int k=0;
	rep(i,1,n) {
		if (k) k--;
		int j=sa[rank[i]-1];
		while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
		h[rank[i]]=k;
	}
}

int query(int now,int pre,int tl,int tr,int l,int r) {
	if (tl==l&&tr==r) return t[now].sum-t[pre].sum;
	int mid=(tl+tr)>>1;
	if (r<=mid) return query(t[now].l,t[pre].l,tl,mid,l,r);
	if (l>mid) return query(t[now].r,t[pre].r,mid+1,tr,l,r);
	return query(t[now].l,t[pre].l,tl,mid,l,mid)+query(t[now].r,t[pre].r,mid+1,tr,mid+1,r);
}

void modify(int &now,int pre,int tl,int tr,int x) {
	t[now=++tot]=t[pre]; t[now].sum++;
	if (tl==tr) return ;
	int mid=(tl+tr)>>1;
	if (x<=mid) modify(t[now].l,t[pre].l,tl,mid,x);
	else modify(t[now].r,t[pre].r,mid+1,tr,x);
}

int get_min(int l,int r) {
	int lg=llgg[r-l];
	return std:: min(min[l][lg],min[r-(1<<lg)][lg]);
}

bool check(int a,int b,int c,int v) {
	int l,r,pl=rank[c],pr=rank[c],mid;
	for (l=1,r=rank[c];l<r;) {
		mid=(l+r)>>1;
		if (get_min(mid,rank[c])<v) l=mid+1;
		else r=mid;
	} pl=r;
	for (l=rank[c],r=n;l<r;) {
		mid=(l+r+1)>>1;
		if (get_min(rank[c],mid)<v) r=mid-1;
		else l=mid;
	} pr=r;
	return query(root[pr],root[(!pl)?0:(pl-1)],1,n,a,b-v+1);
}

int main(void) {
	rep(i,1,N-1) llgg[i]=log2(i);
	int m; scanf("%d%d%s",&n,&m,s+1);
	get_sa(n); get_height(n);
	rep(i,1,n) min[i-1][0]=h[i];
	rep(j,1,17) rep(i,0,n-1) {
		min[i][j]=std:: min(min[i][j-1],min[i+(1<<(j-1))][j-1]);
	}
	rep(i,1,n) modify(root[i],root[i-1],1,n,sa[i]);
	for (;m--;) {
		int a,b,c,d,l,r,ans=0; scanf("%d%d%d%d",&a,&b,&c,&d);
		for (l=0,r=std:: min(b-a+1,d-c+1);l<r;) {
			int mid=(l+r+1)>>1;
			if (check(a,b,c,mid)) l=mid;
			else r=mid-1;
		}
		printf("%d\n", r);
	}
	return 0;
}