loj2059 「TJOI / HEOI2016」字符串

字符串好难啊不会啊

#include <iostream>

#include <cstdio>

using namespace std;

int n, m, rnk[100005], cnt[100005], tmp[100005], p, mx=128, saa[100005], tot, a, b;

int height[100005], gg[19][100005], mlg[100005], rot[100005], c, d;

char ss[100005];

struct Node{

	int l, r, sum;

}nd[2000005];

void sasort(){

    for(int i=0; i<mx; i++)  cnt[i] = 0;

    for(int i=0; i<n; i++)  cnt[rnk[i]]++;

    for(int i=1; i<mx; i++)  cnt[i] += cnt[i-1];

    for(int i=n-1; i>=0; i--)   saa[--cnt[rnk[tmp[i]]]] = tmp[i];

}

void getSa(){

    for(int i=0; i<n; i++){

        rnk[i] = ss[i];

        tmp[i] = i;

    }

    sasort();

    for(int j=1; p<n; j<<=1){

        p = 0;

        for(int i=n-j; i<n; i++)    tmp[p++] = i;

        for(int i=0; i<n; i++)

            if(saa[i]>=j)

                tmp[p++] = saa[i] - j;

        sasort();

        swap(rnk, tmp);

        p = 1;

        rnk[saa[0]] = 0;

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

            if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])

                rnk[saa[i]] = p - 1;

            else

                rnk[saa[i]] = p++;

        mx = p;

    }

}

void getHeight(){

	int h=0;

    for(int i=0; i<n; i++){

        if(h)   h--;

        int j=saa[rnk[i]-1];

        while(ss[i+h]==ss[j+h])   h++;

        height[rnk[i]] = h;

    }

}

void getRmq(){

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

	for(int j=1; j<=17; j++)

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

			if(i+(1<<(j-1))>n)	break;

			gg[j][i] = min(gg[j-1][i], gg[j-1][i+(1<<(j-1))]);

		}

}

int update(int pre, int l, int r, int x){

	int re=++tot;

	nd[re] = nd[pre];

	nd[re].sum++;

	if(l==r)	;

	else{

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

		if(x<=mid)	nd[re].l = update(nd[pre].l, l, mid, x);

		else	nd[re].r = update(nd[pre].r, mid+1, r, x);

	}

	return re;

}

bool query(int pre, int now, int l, int r, int x, int y){

	if(l>=x && r<=y)	return nd[now].sum-nd[pre].sum>0;

	else{

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

		bool re=false;

		if(x<=mid)	re |= query(nd[pre].l, nd[now].l, l, mid, x, y);

		if(mid<y)	re |= query(nd[pre].r, nd[now].r, mid+1, r, x, y);

		return re;

	}

}

int main(){

	cin>>n>>m;

	scanf("%s", ss);

	ss[n++] = 0;

	getSa();

	n--;

	getHeight();

	getRmq();

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

		rot[i] = update(rot[i-1], 1, n, rnk[i-1]);

	while(m--){

		scanf("%d %d %d %d", &a, &b, &c, &d);

		int l=1, r=min(b-a+1, d-c+1), mid, re=0;

		while(l<=r){

			mid = (l + r) >> 1;

			int zuo=rnk[c-1], you=rnk[c-1];

			for(int i=17; i>=0; i--)

				if(zuo>=(1<<i) && gg[i][zuo-(1<<i)+1]>=mid)

					zuo -= 1<<i;

			for(int i=17; i>=0; i--)

				if(you+(1<<i)<=n && gg[i][you+1]>=mid)

					you += 1<<i;

			if(query(rot[a-1], rot[b-mid+1], 1, n, zuo, you))

				re = mid, l = mid + 1;

			else

				r = mid - 1;

		}

		printf("%d\n", re);

	}

	return 0;

}