想复杂 + 频繁犯错

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;
}