P2178 [NOI2015] 品酒大会 题解（评分：8.0）
int08
·
·
题解
前言
"I'm free."
做法与题解区都不同，虽然麻烦，但是毕竟复杂度是对的，而且想法很自然，还是写一写吧！
Solution
题意：给定长为 n 的字符串 s 和长为 n 的数组 A，对于每个 r，求 满足 \text{LCP}(\text{Suffix}(x),\text{Suffix}(y))\ge r,x<y 的数对 (x,y) 数量。
其中 \text{LCP}(x,y) 指字符串 x,y 的最长公共前缀，\text{Suffix}(i) 表示串 s 从第 i 位开始的后缀。
然后记数对 (x,y) 权值为 A_x\times A_y，对于每个 r，求满足上述条件的数对的最大权值。
一、串串题惯常套路
看见要求原串两个后缀的 \text{LCP}，最直接的反应便是启动后缀数组，并计算出 height 数组。
然后 \text{LCP}(\text{Suffix}(x),\text{Suffix}(y))=\min_{i\in [rank_x+1,rank_y]} h_i,rank_x<rank_y 便可求出任意两个后缀的 \text{LCP}。
现在我们就把字符串问题转移为数列问题。
二、具体解决方案
现在相当于询问对于每个 r，有多少满足 \min_{i\in [x+1,y]}h_i \ge r,x<y 的数对 (x,y)。
此时出现三个考虑方向：
第一是分别计算每一位 h_i 对答案贡献。
第二是从大到小枚举 r ，使用并查集维护区间的阻断或者连通性，计算答案是多少。
但是其实正序计算也是可以哒！
我们把 h_i 从小到大排序，并一个一个按原位置加入数组中。
容易发现，加入所有 h_i<i 之后，仍然不包含任何数字的区间，就是对于 r=i 时的一个合法区间。
举个例子：
| s[i] | p | o | n | o | i | i | i | p | o | i |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| sa[i] | 10 | 5 | 6 | 7 | 3 | 9 | 4 | 2 | 8 | 1 |
| h[i] | 0 | 1 | 2 | 1 | 0 | 0 | 2 | 1 | 0 | 2 |
| 加入 0 | 0 | | | | 0 | 0 | | | 0 | |
对于一个连续的空区间，任选其中两点（左端点可以选到左边的数字上），皆是一个合法答案，设其长度为 $l$，对第一问贡献为 $l\times (l+1)\div 2$。
考虑在数组中加入一个数，会对答案产生什么样的影响？
会把一个连续空区间分成两个。
那么对于第一问是简单的，减去原来长区间贡献，分别加入两个短区间贡献即可。
### 三、第二问咋做
仍然考虑一个长区间对于整体的贡献。
上文已经提到，对于一个连续的空区间，任选其中两点（左端点可以选到左边的数字上），皆是一个合法答案。
为了使得权值最大化，显然要选 $A_i$ 最大的两个，或者最小的两个（负负得正）。
这是一个典型的询问区间最大和次大，使用数据结构维护即可。
然后对于区间的贡献，不仅有删除和添加（把一个大区间分成两个后，删除大区间贡献，加入两个小区间贡献），还要实时查询各个区间贡献的最大值，还是用数据结构来维护。
### 四、实现细节
用啥数据结构呢？
询问区间最大次大和最小次小，由于不带修，ST 表即可。
（但是我倍增不熟，赛时怕挂，便使用了线段树来维护）
如何找到左右最靠近的加入过的数，单调栈或者树状数组或者 set 都可以。
（这里建议最后一个，但是我赛时使用了最麻烦的第二个）
如何实时查询贡献最大值并支持加入删除某个数？堆或者 multiset。
时间复杂度都是 $\text{O}(n\log n)$，但是一个 $\log$ 遍地跑，常数贼大。
（实测最慢点 $970$ 到 $1500$ 毫秒不等，通过率高于 $50\%$）。
这个做法最大的区别便是正序枚举 $r$，并使用堆来解决第二问。
贴一个修改过的赛时代码，很唐。
趣事：赛时没有使用 multiset 而用的 set，但是过了所有测试数据，洛谷上被官方数据搞成 $70$ 了。
_"Save me."_
## AC Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define For(l,r,b) for(b=l;b<=r;b++)
#define N 300005
#define inf 1000000007ll
using namespace std;
string s;
int i,j,sa[N],rk[N],rk1[N],sec[N],tot[N],n,h[N];
int tr[N][2];
int a[N],A[N];
vector<int> hp[N];
struct tree{
int l,r,s1,s2,b1,b2;
}t[4*N];
struct an{
int s1,s2,b1,b2;
};
an mi(an x,an y)
{
return {min(x.s1,y.s1),min(max(x.s1,y.s1),min(x.s2,y.s2)),max(x.b1,y.b1),max(min(x.b1,y.b1),max(x.b2,y.b2))};
}
void pushup(int o)
{
an x={t[o*2].s1,t[o*2].s2,t[o*2].b1,t[o*2].b2},y={t[o*2+1].s1,t[o*2+1].s2,t[o*2+1].b1,t[o*2+1].b2};
an xy=mi(x,y);
t[o]={t[o].l,t[o].r,xy.s1,xy.s2,xy.b1,xy.b2};
}
multiset<int> se;
multiset<int>::iterator it;
void build(int l,int r,int o)
{
t[o].l=l;t[o].r=r;
if(l==r)
{
t[o].s1=t[o].b1=A[l];
t[o].s2=inf;
t[o].b2=-inf;
return;
}
int mid=(l+r)>>1;
build(l,mid,o*2);
build(mid+1,r,o*2+1);
pushup(o);
}
an query(int l,int r,int o)
{
if(t[o].l>=l&&t[o].r<=r) return {t[o].s1,t[o].s2,t[o].b1,t[o].b2};
int mid=(t[o].l+t[o].r)>>1;
an ans={inf,inf,-inf,-inf};
if(l<=mid) ans=mi(ans,query(l,r,o*2));
if(r>mid) ans=mi(ans,query(l,r,o*2+1));
return ans;
}
void change(int x,int y,int id)
{
x++;
for(;x<=n;x+=x&-x) tr[x][id]=max(tr[x][id],y);
}
int ask(int x,int id)
{
x++;
int ans=-1;
for(;x>0;x-=x&-x) ans=max(ans,tr[x][id]);
return ans;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cout.tie(0);
cin>>n>>s;
For(1,n,i) cin>>a[i];
s='#'+s;
For(1,n,i) tot[s[i]]++,rk[i]=s[i];
For(1,128,i) tot[i]+=tot[i-1];
for(i=n;i;i--) sa[tot[rk[i]]--]=i;
int sz=128;
for(int k=1;k<=n;k<<=1)
{
int cnt=0;
For(n-k+1,n,i) sec[++cnt]=i;
For(1,n,i) if(sa[i]>k) sec[++cnt]=sa[i]-k;
memset(tot+1,0,sz<<3);
For(1,n,i) ++tot[rk[i]];
For(1,sz,i) tot[i]+=tot[i-1];
for(i=n;i>=1;i--) sa[tot[rk[sec[i]]]--]=sec[i];
memcpy(rk1+1,rk+1,n<<3);
sz=1;
rk[sa[1]]=1;
For(2,n,i) rk[sa[i]]=(rk1[sa[i]]==rk1[sa[i-1]]&&rk1[sa[i]+k]==rk1[sa[i-1]+k])?sz:++sz;
if(sz==n) break;
}
For(1,n,i)
{
int pt=max(0ll,h[rk[i-1]]-1);
while(s[i+pt]==s[sa[rk[i]-1]+pt]) pt++;
h[rk[i]]=pt;
}
h[1]=0;
For(1,n,i) A[i]=a[sa[i]];
For(1,n,i) hp[h[i]].push_back(i);
build(1,n,1);
an as=query(1,n,1);
change(1,1,0);change(0,0,1);
long long ans=(n-1)*n/2,an2=max(as.b1*as.b2,as.s1*as.s2);
cout<<ans<<" "<<an2<<endl;
For(0,n-2,i)
{
for(auto j:hp[i])
{
int lf=ask(j-1,0),rf=n+1-ask(n-j,1);
if(j==1) lf++;
lf++,rf--;
an gx;int gp;
if(rf>=lf)
{
gx=query(lf-1,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
it=se.lower_bound(-gp);
if(gp!=inf*inf&&j!=1)se.erase(se.lower_bound(-gp));
}
ans-=(rf-lf+1)*(rf-lf+2)/2;
ans+=(j+1-lf)*(j-lf)/2;
ans+=(rf-j+1)*(rf-j)/2;
if(j-1>=lf)
{
gx=query(lf-1,j-1,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
if(gp!=inf*inf) se.insert(-gp);
}
if(j+1<=rf)
{
gx=query(j,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
if(gp!=inf*inf) se.insert(-gp);
}
change(j,j,0);change(n+1-j,n+1-j,1);
}
cout<<ans<<" "<<(ans==0?0:(-(*se.lower_bound(-inf*inf))))<<endl;
}
return 0;
}
```
## 后记
写得比较认真的一篇题解。
谨以此题解，为我~~长达四天~~的字符串简单学习作结，也为基本 OI 知识的第一轮学习作结。
_"I won't leave you."_