P2178 品酒大会题解

· · 题解

提供一个切入点不同的后缀数组做法。

首先考虑，假设我们知道一些后缀是两两 k 相似的，并且我们将其全部放在区间 [l,r] 内，能对答案产生多少贡献。

显然，对于方案数，其贡献为 C_{r-l+1}^2；对于美味度，其贡献为这个区间里最大美味度。最大美味度可能是区间最大与次大的乘积，也可能是区间最小与次小的乘积。

而找到两两 k 相似我们可以利用后缀数组，构造出 height 和 sa 数组，同时实现了将两两 k 相似的串放在了一个区间中。这一部分不会的出门右转模板题。

那么我们可以使用线段树，维护区间最大值、次大值、最小值、次小值。即可在区间已知的情况下 O(\log n) 统计贡献。其中线段树的下标基于后缀数组。

tree merge(tree x,tree y){
    if(y.maxn>x.maxn)x.smax=x.maxn,x.maxn=y.maxn;
    else if(y.maxn>x.smax)x.smax=y.maxn;
    if(y.smax>x.maxn)x.smax=x.maxn,x.maxn=y.smax;
    else if(y.smax>x.smax)x.smax=y.smax;
    if(y.minn<x.minn)x.smin=x.minn,x.minn=y.minn;
    else if(y.minn<x.smin)x.smin=y.minn;
    if(y.smin<x.minn)x.smin=x.minn,x.minn=y.smin;
    else if(y.smin<x.smin)x.smin=y.smin;
    return x;
}

现在考虑第二个问题：找区间+统计答案

后缀数组有一个比较常见的策略，即基于 height 分组。我们枚举当前要找 k 相似的 k，那么根据 k 对 height 分组，使得每组 [l,r] 满足 height_{r+1}<k 且 height_{l+1\dots r}\ge k。那么显然，每一组都是一段极长的 k 相似区间。配合线段树统计答案。

复杂度：枚举长度 O(n)，分组 O(n)，查询 O(\log n)，总复杂度 O(n^2\log n)。考虑进一步优化。

很多题解到这里选择倒序枚举、合并区间，但毕竟咱不一定能想到嘛，所以我们仍然顺序枚举、分裂区间。

考虑我们的复杂度瓶颈在哪里。那么分组和枚举的复杂度至少要抠掉一个。

发现一个比较显然的性质：

很好理解，这个基于后缀数组的定义，或者 k 相似的定义都可以证。

这个性质告诉我们：找到一个区间后，不用考虑区间外的数对这个区间分组的影响了。

这是一个很有启发性的结论。那么考虑如何对一个区间重分组。

这个可以根据分组定义直接证得。

根据这两个性质，我们可以得到一种高效的重分组方式：

现在考虑如何找到区间内所有 height=k 的位置。比较直接的想法是直接在桶里去二分找，或者用 set 维护位置。当然都可以，不过本人一时脑抽，写了个平衡树。

我们对每个 height 值开一个平衡树，查找时相当于找到上一个断点的后继位置，直到找不到下一个后继或者下一个后继位置超过 r。由于每个位置 height 唯一，且至多会在一个区间内被询问。所以每个位置最多成为一次查询前驱的答案。总复杂度 O(n\log n)，均摊为单次 O(\log n)。

此外，我们舍弃无法切割的继承，每次直接找到下一个会产生新的切割区间的相似度进行转移。这一段的区间相同，贡献一定相同，放在答案区间上等同于区间加和区间取 \max。这一部分可以利用差分，也可以利用线段树。代码里是线段树做法。

至于找到下一个切分点，其实就是 \min\{height_{l+1\dots r}\}+1。直接上 ST 表就可。

这样划分区间的复杂度看似很玄学，但是可以证明是 O(n) 级别的！

证明：考虑每个区间。长度上升时，要么新区间直接继承，要么区间被切割成若干段。结束的情况有两种，即 n 相似和长度为 1，由于 height\le n-1，所以这两种情况本质相同。因为继承已经被我们统一处理了，所以只考虑切割。每次转移必定产生区间切割，并且一个位置至多被切 1 次，所以我们恰好切了 n-1 次，即产生至多 n-1 次有效转移。所以有效区间个数为 O(n) 级别。

对每个区间处理单次复杂度 O(\log n)，总复杂度 O(n\log n)。

对于边界细节，很多题解都有强调，如各类初值 \pm 10^{18} 之类。

此外，考虑到标记永久化比标记下放好写，所以我对答案线段树采用标记永久化的方式统计答案。

因为同时用了三棵树，所以代码可能略长。在必要的地方添加注释了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
const int inf=1<<30;
const long long inff=1ll<<60;
using namespace std;
struct treap{
    int son[2],val;
    long long key;
}trp[500001];
struct tree{
    long long maxn,smax;
    long long minn,smin;
    //smax/min 表示次大/次小值。
}tre[4000001];
struct ans{
    long long tag,rev;
    //tag 维护方案数询问，rev 维护最值询问。
}tr[4000001];
int root[400001],size;
//每个 root 代表 height 的一种取值，平衡树内维护下标。
//treap 部分
void rotate(int &k,int fx){
    int x=trp[k].son[fx^1];
    trp[k].son[fx^1]=trp[x].son[fx];
    trp[x].son[fx]=k;
    k=x;
}
void insert(int &k,int val){
    if(!k){
        k=++size;
        trp[k].key=rand();
        trp[k].val=val;
        return;
    }
    if(trp[k].val==val)return;
    else if(trp[k].val>val){
        insert(trp[k].son[0],val);
        if(trp[k].key<trp[trp[k].son[0]].key)rotate(k,1);
    }
    else{
        insert(trp[k].son[1],val);
        if(trp[k].key<trp[trp[k].son[1]].key)rotate(k,0);
    }
}
int qlas(int id,int val){
    int x=root[id],res=0;
    while(x){
        if(trp[x].val<=val)x=trp[x].son[1];
        else res=trp[x].val,x=trp[x].son[0];
    }
    return res;
}
//后缀数组全家桶
int n,sa[500001],rk[500001],height[500001];
int tsa[500001],trk[1000001],cnt[500001];
int a[500001],st[500001][20],lg[500001];
char s[500001];
long long max(long long x,long long y){
    return x>y?x:y;
}
long long min(long long x,long long y){
    return x<y?x:y;
}
int qmin(int l,int r){
    int k=lg[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
tree merge(tree x,tree y){
    if(y.maxn>x.maxn)x.smax=x.maxn,x.maxn=y.maxn;
    else if(y.maxn>x.smax)x.smax=y.maxn;
    if(y.smax>x.maxn)x.smax=x.maxn,x.maxn=y.smax;
    else if(y.smax>x.smax)x.smax=y.smax;
    if(y.minn<x.minn)x.smin=x.minn,x.minn=y.minn;
    else if(y.minn<x.smin)x.smin=y.minn;
    if(y.smin<x.minn)x.smin=x.minn,x.minn=y.smin;
    else if(y.smin<x.smin)x.smin=y.smin;
    return x;
}
void build(int k,int l,int r){
    tre[k].maxn=tre[k].smax=-inf;
    tre[k].minn=tre[k].smin=inf;
    tr[k].rev=-inff;
    //不处理 0 相似答案很大一个原因就是两个线段树的结构相同，可以少打一个 build
    if(l==r){
        tre[k].maxn=tre[k].minn=a[sa[l]];
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tre[k]=merge(tre[k<<1],tre[k<<1|1]);
}
tree query(int k,int l,int r,int x,int y){
    //这四个查询会相互影响，不方便单独查询。
    //所以我们直接把区间对应的线段树提取出来。
    if(l>=x&&r<=y)return tre[k];
    int mid=l+r>>1;
    if(mid>=y)return query(k<<1,l,mid,x,y);
    if(x>mid)return query(k<<1|1,mid+1,r,x,y);
    return merge(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
}
void modify(int k,int l,int r,int x,int y,long long w1,long long w2){
    //对答案线段树的更新，w1 是方案，w2 是最值
    if(l>=x&&r<=y){
        tr[k].tag+=w1;
        tr[k].rev=max(tr[k].rev,w2);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(k<<1,l,mid,x,y,w1,w2);
    if(mid<y)modify(k<<1|1,mid+1,r,x,y,w1,w2);
}
long long qmax(int k,int l,int r,int x){
    if(l==r)return tr[k].rev;
    int mid=l+r>>1;
    long long res=tr[k].rev;
    if(x<=mid)res=max(res,qmax(k<<1,l,mid,x));
    else res=max(res,qmax(k<<1|1,mid+1,r,x));
    return res;
}
long long qsum(int k,int l,int r,int x){
    if(l==r)return tr[k].tag;
    int mid=l+r>>1;
    long long res=tr[k].tag;
    if(x<=mid)res+=qsum(k<<1,l,mid,x);
    else res+=qsum(k<<1|1,mid+1,r,x);
    return res;
}
void solve(int l,int r,int minx){
    //主体部分。表示当前处理区间 [l,r] 是 minx 相似的。
    if(l>=r||minx==n)return;
    tree rst=query(1,1,n,l,r);
    int nxt=qmin(l+1,r);
    //直接找到下一个切点长度
    long long res=max(rst.maxn*rst.smax,rst.minn*rst.smin),as=1ll*(r-l+1)*(r-l)/2;
    if(minx)modify(1,1,n,minx,nxt,as,res);
    //对 0 相似单独解决原因见 build 函数。
    //0 相似是整个区间，可以 O(1) 解决。
    int ps=l;
    while(ps<=r){
        int t=qlas(nxt,ps);
        if(!t||t>r)t=r+1;
        solve(ps,t-1,nxt+1);
        ps=t;
    }
}
int main(){
    srand((unsigned)time(NULL));
    int i,j;
    scanf("%d%s",&n,s+1);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)rk[i]=s[i]-'a'+1,cnt[rk[i]]++;;
    for(i=1;i<=26;i++)cnt[i]+=cnt[i-1];
    for(i=n;i;i--)sa[cnt[rk[i]]--]=i;
    for(i=1;i<=n;i++){
        if(s[sa[i]]==s[sa[i-1]])rk[sa[i]]=rk[sa[i-1]];
        else rk[sa[i]]=rk[sa[i-1]]+1;
    }
    for(j=1;j<n;j*=2){
        memcpy(tsa,sa,sizeof(sa));
        memcpy(trk,rk,sizeof(rk));
        int tot=0;
        for(i=n;i>n-j;i--)sa[++tot]=i;
        for(i=1;i<=n;i++)if(tsa[i]>j)sa[++tot]=tsa[i]-j;
        for(i=1;i<=n;i++)rk[i]=trk[sa[i]];
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=n;i++)cnt[rk[i]]++;
        for(i=1;i<=n;i++)cnt[i]+=cnt[i-1];
        for(i=n;i;i--)tsa[cnt[rk[i]]--]=sa[i];
        memcpy(sa,tsa,sizeof(sa));
        for(i=1;i<=n;i++){
            if(trk[sa[i]]==trk[sa[i-1]]&&trk[sa[i]+j]==trk[sa[i-1]+j])rk[sa[i]]=rk[sa[i-1]];
            else rk[sa[i]]=rk[sa[i-1]]+1;
        }
        if(rk[sa[n]]==n){
            for(i=1;i<=n;i++)sa[rk[i]]=i;
            break;
        }
    }
    int len=0;
    for(i=1;i<=n;i++){
        if(len)len--;
        while(s[i+len]==s[sa[rk[i]-1]+len])len++;
        height[rk[i]]=len;
    }
    for(i=1;i<=n;i++)insert(root[height[i]],i);
    for(i=1;i<=n;i++)st[i][0]=height[i];
    for(i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(i=1;i<=lg[n];i++)for(j=1;j+(1<<i)-1<=n;j++)st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
    build(1,1,n);
    solve(1,n,0);
    tree ss=query(1,1,n,1,n);
    printf("%lld %lld\n",1ll*n*(n-1)/2,max(ss.maxn*ss.smax,ss.minn*ss.smin));
    for(i=1;i<n;i++){
        long long num=qsum(1,1,n,i);
        printf("%lld %lld\n",num,num?qmax(1,1,n,i):0);
        //有方案，我们输出方案；没有方案，我们输出约定的 0
    }
}