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;
}