[NOI2015] 品酒大会 题解

注意到题解区没有分治做法。

首先可以先建立后缀数组和height数组，并对height数组建立st表，那么对于 $r$ 相似的两杯酒 $p,q$，在后缀数组的 $[rk[p],rk[q])$ 中（默认 $rk[p]<rk[q]$）最小的 $height[i]=r(p \le i < q)$（即后缀 $p,q$ 的 $LCP$）。

那么反过来想，在区间 $[L,R]$ 中，设最小的 $height$ 的位置为 $x$（即排名为 $x$ 和 $x+1$ 的后缀之间的LCP最短），那么对于所有跨过 $x,x+1$ 的区间 $[p,q](L\le p \le x)(x+1\le q \le R)$，$p$ 和 $q$ 都是 $r$ 相似的，即统计出有 $(x-L+1)\times(R-x)$ 对 $p,q$ 的答案为 $r$，然后递归分治求解区间 $[L,x]$ 和 $[x+1,R]$，这样第一问就做完了。

对于第二问，先按 $sa[i]$ 的顺序建立出 $a[i]$ 的最大值和最小值的st表。在求解跨过 $x,x+1$ 的区间数量时，所有满足条件的区间 $[p,q](L\le p \le x)(x+1\le q \le R)$ 的可能美味值为 $a[p]\times a[q]$，因为我们记录了st表，可以直接求出 $a[p]\times a[q]$ 的最大值（注意 $a[i]$ 可能为负，最大最小值都要求）。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=3e5+10;
int n,m,p,sa[mxn],rk[mxn],oldrk[mxn],cnt[mxn],id[mxn],st[mxn][25],sti[mxn][25],lg2[mxn];
ll a[mxn],mx[mxn],ans[mxn],st2[mxn][25],st3[mxn][25];
string s;
void get_SA(){//求SA及height 
	m=255;
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;p<n;w<<=1,m=p){
		int cur=0;
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	} 
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==n)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]+1]+k])k++;
		st[rk[i]][0]=k;
		sti[rk[i]][0]=rk[i];
	}
}
void init_st(){//建st表 
	for(int i=1;i<=n;i++)st3[rk[i]][0]=st2[rk[i]][0]=a[i];//注意是按sa[i]的顺序建的 
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<n;i++){
			if(st[i][j-1]<st[i+(1<<j-1)][j-1]){
				st[i][j]=st[i][j-1];
				sti[i][j]=sti[i][j-1];
			}
			else{
				st[i][j]=st[i+(1<<j-1)][j-1];
				sti[i][j]=sti[i+(1<<j-1)][j-1];
			}
		}
	}
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st2[i][j]=max(st2[i][j-1],st2[i+(1<<j-1)][j-1]);
			st3[i][j]=min(st3[i][j-1],st3[i+(1<<j-1)][j-1]);
		}
	}
}
int get(int l,int r){
	int d=lg2[r-l+1];
	if(st[l][d]<st[r-(1<<d)+1][d])return st[l][d];
	return st[r-(1<<d)+1][d];
}
int geti(int l,int r){
	int d=lg2[r-l+1];
	if(st[l][d]<st[r-(1<<d)+1][d])return sti[l][d];
	return sti[r-(1<<d)+1][d];
}
ll get2(int l,int r){
	int d=lg2[r-l+1];
	if(st2[l][d]>st2[r-(1<<d)+1][d])return st2[l][d];
	return st2[r-(1<<d)+1][d];
}
ll get3(int l,int r){
	int d=lg2[r-l+1];
	if(st3[l][d]<st3[r-(1<<d)+1][d])return st3[l][d];
	return st3[r-(1<<d)+1][d];
}
void solve(int l,int r){//分治求解（此处solve(l,r)表示求解区间[l,r+1]）
	if(l>r)return ;
	if(l==r){
		int p=st[l][0];
		mx[p]=max(mx[p],a[sa[l]]*a[sa[l+1]]);
		ans[p]++;
		return ;
	}
	ll v=get(l,r),p=geti(l,r);
	mx[v]=max(mx[v],max(get2(l,p)*get2(p+1,r+1),get3(l,p)*get3(p+1,r+1)));
	ans[v]+=(p-l+1)*(r-p+1);
	solve(l,p-1);
	solve(p+1,r);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	cin>>s;
	for(int i=1;i<=n;i++)cin>>a[i];
	s=" "+s;
	get_SA();
	init_st();
	memset(mx,-0x3f,sizeof(mx));
	solve(1,n-1);
	for(int i=n-2;i>=0;i--){
		ans[i]+=ans[i+1];
		mx[i]=max(mx[i],mx[i+1]);
	}
	for(int i=0;i<n;i++){
		if(ans[i]){
			cout<<ans[i]<<" "<<mx[i]<<'\n';
		}
		else{
			cout<<"0 0\n";
		}
	}
	return 0;
}

/*
1.Binary Search?
2.Dynamic Program?
3.Data Structure?
4.Monotonic?
5.Modulo?
6.Tarjan?
7.Offline?
8.ChthollyTree? (Mo's Algorithm?)
9.SimulateAnneal? (That's not possible)



1.Think Backward?
2.Make Charts?
3.Find Features?
4.Widen Constraints?
5.Answer = All - Illegal
6.Skip the process.Focus on the result
*/
#include <bits/stdc++.h>

#define int long long

using namespace std;

int now = 0, num = LLONG_MIN, len = 0;

array<char, 300100> str;

array<int, 300100> ans1, ans2, fa, sizes, minx, maxn, val;

array<vector<int>, 300100> block;

struct SuffixArray {
    array<char, 300100> text;

    array<int, 600100> id, height, sa, rk, rk_, cnt;

    void init() {
        int len = strlen(text.data() + 1), limit = 128, tmp = 0;

        for (int i = 1; i <= 2 * len; ++ i)
            id[i] = height[i] = sa[i] = rk_[i] = rk[i] = cnt[i] = 0;

        for (int i = 1; i <= len; ++ i)
            rk[i] = text[i], ++ cnt[rk[i]];

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

        for (int i = len; i >= 1; -- i)
            sa[cnt[rk[i]] --] = i;

        for (int it = 1;; it <<= 1, limit = tmp) {
            int tot = 0;

            for (int i = len - it + 1; i <= len; ++ i)
                id[++ tot] = i;

            for (int i = 1; i <= len; ++ i)
                if (sa[i] > it)
                    id[++ tot] = sa[i] - it;

            memset(cnt.data(), 0, sizeof cnt);

            for (int i = 1; i <= len; ++ i)
                ++ cnt[rk[i]];

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

            for (int i = len; i >= 1; -- i)
                sa[cnt[rk[id[i]]] --] = id[i];

            memcpy(rk_.data(), rk.data(), sizeof rk_);

            tmp = 0;

            for (int i = 1; i <= len; ++ i) {
                if (rk_[sa[i]] == rk_[sa[i - 1]] && rk_[sa[i] + it] == rk_[sa[i - 1] + it])
                    rk[sa[i]] = tmp;
                else
                    rk[sa[i]] = ++ tmp;
            }

            if (tmp == len)
                break;
        }

        for (int i = 1; i <= len; ++ i)
            rk[sa[i]] = i;

        for (int i = 1; i <= len; ++ i) {
            if (rk[i] == 1)
                continue;

            int it = max(1ll, height[rk[i - 1]] - 1);

            while (text[i + it - 1] == text[sa[rk[i] - 1] + it - 1])
                ++ it;

            -- it;

            height[rk[i]] = it;
        }
    }
} SA;

int find(int x) {
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];

    return x;
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);

    now += sizes[rx] * sizes[ry];
    num = max({num, maxn[rx] * maxn[ry], minx[rx] * minx[ry]});
    fa[ry] = rx;
    maxn[rx] = max(maxn[rx], maxn[ry]);
    minx[rx] = min(minx[rx], minx[ry]);
    sizes[rx] += sizes[ry];

    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> len;

    cin >> (str.data() + 1);

    for (int i = 1; i <= len; ++ i)
        cin >> val[i];

    SA.text = str;
    SA.init();

    for (int i = 1; i <= len; ++ i)
        fa[i] = i, sizes[i] = 1, maxn[i] = minx[i] = val[SA.sa[i]], block[SA.height[i]].emplace_back(i);

    for (int i = len - 1; i >= 0; -- i) {
        for (int x = 0; x < block[i].size(); ++ x) {
            if (block[i][x] - 1)
                merge(block[i][x], block[i][x] - 1);
        }

        if (now)
            ans1[i] = now, ans2[i] = num;
    }

    for (int i = 0; i <= len - 1; ++ i)
        cout << ans1[i] << ' ' << ans2[i] << '\n';

    cout << endl;

    return 0;
}