Description：

给两个串 $A$ 和 $B$ ，每次询问给出 $l_1,r_1,l_2,r_2$ ，设 $S=A[l_1:r_1],T=B[l_2:r_2]$ ，每次可以在 $S$ 中删除一个和 $T$ 相等的子串，获得 $K-i$ 的收益， $i$ 是字串的起始位置在 $A$ 中的下标，求获得收益的最大值。

$1\leqslant n,q\leqslant 10^5,51\leqslant r-l\leqslant 2\times 10^3$ 的询问不超过 $11000$ 个。

Solution：

看数据范围估计就是让你阈值分块。

首先一个贪心是不停找第一次出现的位置直到贡献为负。

首先对于 $r-l$ 很大的询问我们可以建立 $SA$ ，然后就是在合法的区间内找一个在上一次之后最靠前的位置，二位偏序可以用主席树上二分，当 $r-l>2\times 10^3$ 的时候单次复杂度才 $100\log n$ ，当 $51\leqslant r-l\leqslant 2\times 10^3$ 的时候数据随机，都可以这样做。

当 $r-l$ 很小的时候总共只有 $50$ 种不同的长度，我们考虑询问实际上就是每次向后找第一个相同的串，那么我们建立 $50$ 棵树，每个点的父亲是这个点往后 $l$ 个位置这个串下一次出现的位置，然后每次询问树上倍增就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

#define I inline

#define R register

I int rd()

{

	R int res = 0,f = 1;R char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

I char getc()

{

	R char c = getchar();

	while(!islower(c))c = getchar();

	return c;

}

int n,m,K;

#define MAXN 400010

char A[MAXN],B[MAXN];

char s[MAXN];

int tot = 0;

namespace SA

{

	int sa[MAXN],rnk[MAXN],height[MAXN];

	int c[MAXN],c1[MAXN],c2[MAXN];

	int f[MAXN][19];

	int lg[MAXN];

	I void make_SA(int n,int m)

	{

		R int *x = c1,*y = c2;

		R int p;

		for(R int i = 1;i <= m;++i)c[i] = 0;

		for(R int i = 1;i <= n;++i)++c[x[i] = s[i]];

		for(R int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(R int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

		for(R int k = 1;k <= n;k = k << 1)

		{

			p = 0;

			for(R int i = 1;i <= n;++i)y[i] = 0;

			for(R int i = n - k + 1;i <= n;++i)y[++p] = i;

			for(R int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

			for(R int i = 1;i <= m;++i)c[i] = 0;

			for(R int i = 1;i <= n;++i)++c[x[y[i]]];

			for(R int i = 1;i <= m;++i)c[i] += c[i - 1];

			for(R int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

			p = 1;

			swap(x,y);

			x[sa[1]] = 1;

			for(R int i = 2;i <= n;++i)

			{

				x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

			}

			if(p >= n)break;

			m = p;

		}

		for(R int i = 1;i <= n;++i)rnk[sa[i]] = i;

		R int k = 0;

		for(R int i = 1;i <= n;++i)

		{

			if(rnk[i] == 1)continue;

			if(k)--k;

			R int j = sa[rnk[i] - 1];

			while(j + k <= n && i + k <= n && s[j + k] == s[i + k])++k;

			height[rnk[i]] = k;

		}

		for(R int i = 1;i <= n;++i)f[i][0] = height[i];

		for(R int k = 1,l = 1;k <= 18;++k,l = l << 1)

			for(R int i = 1;i <= n - l * 2 + 1;++i)

				f[i][k] = min(f[i][k - 1],f[i + l][k - 1]);

		for(R int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

		return;

	}

	I int LCP(int a,int b)

	{

		if(a == b)return 2 * n - sa[a];

		++a;

		R int l = lg[b - a + 1];

		R int res = min(f[a][l],f[b - (1 << l) + 1][l]);

		return res;

	}

	I int getl(int p,int lcp)

	{

		R int l = 1,r = p,mid;

		while(l < r)

		{

			mid = ((l + r) >> 1);

			if(LCP(mid,p) >= lcp)r = mid;

			else l = mid + 1;

		}

		return l;

	}

	I int getr(int p,int lcp)

	{

		R int l = p,r = 2 * n,mid;

		while(l < r)

		{

			mid = ((l + r + 1) >> 1);

			if(LCP(p,mid) >= lcp)l = mid;

			else r = mid - 1;

		}

		return r;

	}

}

namespace FT

{

	struct node

	{

		int lc,rc;

		int sum;

	}t[MAXN * 32];

	int ptr = 0;

	I int newnode(){return ++ptr;}

	int root[MAXN];

	#define mid ((l + r) >> 1)

	I void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	I void insert(int &rt,int p,int l,int r)

	{

		R int k = newnode();t[k] = t[rt];rt = k;

		++t[rt].sum;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	I int query(int rtr,int rtl,int p,int l,int r)

	{

		if(t[rtr].sum - t[rtl].sum == 0)return 0;

		if(l == r)return l;

		R int res = 0;

		if(p <= mid)res = query(t[rtr].lc,t[rtl].lc,p,l,mid);

		if(res == 0)res = query(t[rtr].rc,t[rtl].rc,p,mid + 1,r);

		return res;

	}

}

I int calc(int l,int r,int p)

{

	if(p >= n)return 0;

	R int lef = SA::getl(SA::rnk[l + n],r - l + 1);

	R int rig = SA::getr(SA::rnk[l + n],r - l + 1);

	R int res = FT::query(FT::root[rig],FT::root[lef - 1],p,1,n);

	if(res + r - l > n)return 0;

	else return res;

}

namespace DT

{

	int f[MAXN][18];

	long long cnt[MAXN][18];

}

struct query

{

	int l1,r1,l2,r2,id;

}q[MAXN];

int qnum = 0;

int vec[52][MAXN];

long long ans[MAXN];

I long long work2(int l1,int r1,int l2,int r2)

{

	R long long ans = 0;

	R int cur = l1;

	while(true)

	{

		R int nxt = calc(l2,r2,cur);

		cur = nxt + r2 - l2 + 1;

		if(nxt == 0)break;

		if(nxt + r2 - l2 > r1)break;

		if(K - nxt < 0)break;

		ans += K - nxt;

	}

	return ans;

}

int pos[MAXN];

int main()

{

	scanf("%d%d",&n,&K);

	for(R int i = 1;i <= n;++i)A[i] = getc();

	for(R int i = 1;i <= n;++i)B[i] = getc();

	for(R int i = 1;i <= n;++i)s[++tot] = A[i];

	for(R int i = 1;i <= n;++i)s[++tot] = B[i];

	SA::make_SA(2 * n,256);

	FT::build(FT::root[0],1,n);

	for(R int i = 1;i <= 2 * n;++i)

	{

		FT::root[i] = FT::root[i - 1];

		if(SA::sa[i] <= n)FT::insert(FT::root[i],SA::sa[i],1,n);

	}

	scanf("%d",&m);

	R int l1,r1,l2,r2;

	for(R int i = 1;i <= m;++i)

	{

		l1 = rd();r1 = rd();l2 = rd();r2 = rd();

		if(r2 - l2 + 1 <= 51)

		{

			q[++qnum] = (query){l1,r1,l2,r2,i};

			int len = r2 - l2 + 1;

			vec[len][++vec[len][0]] = qnum;

		}

		else

		{

			ans[i] = work2(l1,r1,l2,r2);

		}

	}

	for(R int i = 1;i <= n;++i)DT::cnt[i][0] = K - i;

	for(R int l = 1;l <= 51;++l)

	{

		if(vec[l][0] == 0)continue;

		for(R int le = 1,ri = le;le <= 2 * n;ri = le = ri + 1)

		{

			while(SA::height[ri + 1] >= l)++ri;

			pos[0] = 0;

			for(int i = le;i <= ri;++i)if(SA::sa[i] + l - 1 <= n)pos[++pos[0]] = SA::sa[i];

			sort(pos + 1,pos + 1 + pos[0]);

			for(int i = 1,j = 1;i <= pos[0];++i)

			{

				while(j <= pos[0] && pos[j] - pos[i] < l)++j;

				if(j > pos[0])DT::f[pos[i]][0] = 0;

				else DT::f[pos[i]][0] = pos[j];

			}

		}

		R int lim = SA::lg[n / l];

		for(R int k = 1;k <= lim;++k)

		{

			for(R int i = 1;i <= n;++i)

			{

				DT::f[i][k] = DT::f[DT::f[i][k - 1]][k - 1];

				DT::cnt[i][k] = DT::cnt[i][k - 1] + DT::cnt[DT::f[i][k - 1]][k - 1];

			}

		}

		for(R int it = 1;it <= vec[l][0];++it)

		{

			R int k = vec[l][it];

			R int l1 = q[k].l1,r1 = q[k].r1,l2 = q[k].l2,r2 = q[k].r2;

			R int cur = calc(l2,r2,l1);

			if(cur == 0)

			{

				ans[q[k].id] = 0;

				continue;

			}

			R long long res = 0;

			for(R int i = lim;i >= 0;--i)

			{

				if(DT::f[cur][i] != 0 && K - DT::f[cur][i] > 0 && DT::f[cur][i] + r2 - l2 <= r1)

				{

					res += DT::cnt[cur][i];

					cur = DT::f[cur][i];

				}

			}

			if(cur + r2 - l2 <= r1)res += K - cur;

			ans[q[k].id] = res;

		}

	}

	for(R int i = 1;i <= m;++i)printf("%lld\n",ans[i]);

	return 0;

}