LP2178 [NOI2015]品酒大会 [SA]
想复杂 + 频繁犯错
Problem
https://www.luogu.org/problemnew/show/P2178
Solution
求 hei 然后转化成了对 hei 处理问题。
可以发现这是一个包含问题,因此可以前缀和。
将 hei 从大到小排序,然后并查集维护两边的最大最小值和大小。
一开始是这么想的,但细节太多,调了一个上午。
才知道有这种做法,可以以原本的序列为并查集维护,这样就好维护得多。
以及直到现在还在犯这种爆 int 的错误。
Code
// Code by ajcxsu
// Problem: wine
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(), pl=0; x=0;
while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
const int N=3e5+10;
typedef long long ll;
char s[N];
int x[N], y[N], sa[N], c[N], n, hei[N], w[N], m;
int fa[N];
ll a1[N], a2[N], w1[N], w2[N], siz[N], rk[N];
struct Node { int x, hei; } no[N];
bool cmp(const Node &a, const Node &b) { return a.hei>b.hei; }
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
void Union(int a, int b) {
int af=Find(a), bf=Find(b);
if(af==bf) return;
if(rk[af]>rk[bf]) swap(af, bf);
fa[af]=bf, rk[bf]=max(rk[af]+1, rk[bf]);
w1[bf]=max(w1[bf], w1[af]);
w2[bf]=min(w2[bf], w2[af]);
siz[bf]+=siz[af];
}
void gsa() {
for(int i=1;i<=n;i++) c[x[i]=s[i-1]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
int num;
for(int k=1;k<=n;k<<=1) {
num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
fill(c, c+m+1, 0);
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
swap(x, y);
x[sa[1]]=1, num=1;
for(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]?num:++num);
if(num==n) break;
m=num;
}
int k=0, j;
for(int i=1;i<=n;i++) {
if(x[i]==1) continue;
j=sa[x[i]-1];
if(k) k--;
while(s[j-1+k]==s[i-1+k]) k++;
hei[x[i]]=k;
}
}
int main() {
m=520;
gn(n), scanf("%s", s);
for(int i=1;i<=n;i++) gn(w[i]);
fill(siz+1, siz+1+n, 1);
gsa();
for(int i=1;i<=n;i++) no[i]={i, hei[i]};
for(int i=1;i<=n;i++) w1[i]=w2[i]=w[sa[i]];
sort(no+1, no+1+n, cmp), memset(a2, -0x3f, sizeof(a2));
int lf, rf, ls, rs;
for(int i=1;i<=n;i++)
if(no[i].x>1) {
lf=Find(no[i].x-1), rf=Find(no[i].x), ls=siz[lf], rs=siz[rf];
assert(lf!=rf);
a1[no[i].hei]+=1ll*ls*rs;
a2[no[i].hei]=max(a2[no[i].hei], max(max(w1[lf]*w1[rf], w2[lf]*w2[rf]), max(w1[lf]*w2[rf], w2[lf]*w1[rf])));
Union(lf, rf);
}
for(int i=n-1;i>=0;i--) a1[i]+=a1[i+1], a2[i]=max(a2[i], a2[i+1]);
a1[0]=1ll*n*(n-1)>>1;
for(int i=0;i<n;i++) printf("%lld %lld\n", a1[i], (a1[i]?a2[i]:0));
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-2178.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆