这一题是个后缀数组

立下flag:在最近的8天里,每日blog至少一更碎碎念

所以,这一题就是求出lcp以后并查集乱搞就行了..

考场上并没想到lcp也是可惜,另外n log²n看起来不是完全不能过..至少uoj和bzoj都过了,lg挂了不明为何

下次写个O(n log n)或者O(n)的试试吧..

lcp的性质也真是神奇..长见识了..

反正这样就是过了..

解法:

1,求lcp

2,倒序求答案

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int x;
    int y;
    int id;
    friend bool operator < (const node &a,const node &b)
    {
        return a.y<b.y;
    }
};
node b[300005];
char a[300005];
int n;
int c[300005];
int val[300005];
void suffix_sort(int xx)
{
    if (xx>=n) return;
    int i;
    for (i=0;i<n;i++)
    {
        if ((i==0)||(b[i].x>b[i-1].x)||(b[i].y>b[i-1].y))
        {
            c[b[i].id]=i;
        }
        else
        {
            c[b[i].id]=c[b[i-1].id];
        }
    }
    for (i=0;i<n;i++)
    {
        b[i].x=c[b[i].id];
        if (b[i].id+xx<n)
        {
            b[i].y=c[b[i].id+xx];
        }
        else
        {
            b[i].y=-1;
        }
    }
    int last=0;
    for (i=1;i<n;i++)
    {
        if (b[i].x!=b[i-1].x)
        {
            sort(b+last,b+i);
            last=i;
        }
    }
    sort(b+last,b+i);
    suffix_sort(xx*2);
}
int lcp[300005];
struct nodes
{
    int size;
    int id;
    int max_val1;
    int max_val2;
    int min_val1;
    int min_val2;
    nodes * last;
    nodes * next;
};
struct lcps
{
    int num1;
    int num2;
    int times;
    friend bool operator < (const lcps &a,const lcps &b)
    {
        return a.times>b.times;
    }
};
lcps g[300005];
nodes f[300005];
const int inf=1000000007;
long long ans1[300005];
long long ans2[300005];
int father[300005];
void link(int x,int y,int i)
{
    int temp=x;
    for (;;)
    {
        if (father[temp]==-1) break;
        temp=father[temp];
    }
    for (;x!=temp;)
    {
        int now=father[x];
        father[x]=temp;
        x=now;
    }
    temp=y;
    for (;;)
    {
        if (father[temp]==-1) break;
        temp=father[temp];
    }
    for (;y!=temp;)
    {
        int now=father[y];
        father[y]=temp;
        y=now;
    }
    ans1[i]-=((long long)f[x].size*(f[x].size-1)/2);
    ans1[i]-=((long long)f[y].size*(f[y].size-1)/2);
    f[x].size+=f[y].size;
    ans1[i]+=((long long)f[x].size*(f[x].size-1)/2);
    if (f[y].max_val1>f[x].max_val1)
    {
        f[x].max_val2=f[x].max_val1;
        f[x].max_val1=f[y].max_val1;
    }
    else if (f[y].max_val1>f[x].max_val2)
    {
        f[x].max_val2=f[y].max_val1;
    }
    if (f[y].max_val2>f[x].max_val2)
    {
        f[x].max_val2=f[x].max_val2;
    }
    if (f[y].min_val1<f[x].min_val1)
    {
        f[x].min_val2=f[x].min_val1;
        f[x].min_val1=f[y].min_val1;
    }
    else if (f[y].min_val1<f[x].min_val2)
    {
        f[x].min_val2=f[y].min_val1;
    }
    if (f[y].min_val2<f[x].min_val2)
    {
        f[x].min_val2=f[x].min_val2;
    }
    long long t=max((long long)f[x].max_val1*f[x].max_val2,(long long)f[x].min_val1*f[x].min_val2);
    if (ans1[i]==1)
    {
        ans2[i]=t;
    }
    else if (ans2[i]<t)
    {
        ans2[i]=t;
    }
    f[x].next=f[y].next;
    f[y].next->last=&f[x];
    father[y]=x;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d",&n);
    scanf("%s",a);
    n=strlen(a);
    int i;
    for (i=0;i<n;i++)
    {
        b[i].y=a[i];
        b[i].id=i;
        scanf("%d",&val[i]);
    }
    sort(b,b+n);
    suffix_sort(1);
    for (i=0;i<n;i++)
    {
        if ((i==0)||(b[i].x>b[i-1].x)||(b[i].y>b[i-1].y))
        {
            c[b[i].id]=i;
        }
        else
        {
            c[b[i].id]=c[b[i-1].id];
        }
    }
    for (i=0;i<n;i++)
    {
        //printf("%d ",b[i].id+1);
        int last;
        if ((i==0)||(lcp[i-1]==0))
        {
            last=0;
        }
        else
        {
            last=lcp[i-1]-1;
        }
        if (c[i]==0) continue;
        for (;a[last+i]==a[last+b[c[i]-1].id];last++) ;
        lcp[i]=last;
    }
    for (i=1;i<n;i++)
    {
        g[i].num1=b[i-1].id;
        g[i].num2=b[i].id;
        g[i].times=lcp[b[i].id];
    }
    sort(g+1,g+n);
    int j;
    nodes temp;
    memset(father,-1,sizeof(father));
    for (j=0;j<n;j++)
    {
        i=b[j].id;
        if (j!=0) f[i].last=&f[b[j-1].id];
        if (j!=n-1) f[i].next=&f[b[j-1].id];
        f[i].size=1;
        f[i].max_val1=val[i];
        f[i].max_val2=-inf;
        f[i].min_val1=val[i];
        f[i].min_val2=inf;
    }
    f[b[0].id].last=&temp;
    f[b[n-1].id].next=&temp;
    int now=1;
    for (i=n-1;i>=0;i--)
    {
        ans1[i]=ans1[i+1];
        ans2[i]=ans2[i+1];
        for (;now<n;)
        {
            if (g[now].times<i) break;
            link(g[now].num1,g[now].num2,i);
            now++;
        }
    }
    ios::sync_with_stdio(false);
    for (i=0;i<n;i++)
    {
        cout<<ans1[i]<<" "<<ans2[i]<<'\n';
    }
    return 0;
}