BZOJ4199 品酒大会

发表于 | 更新于

题目

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 n 杯鸡尾酒。这 n 杯鸡尾酒排成一行，其中第 i 杯酒 （1≤i≤n） 被贴上了一个标签 si，每个标签都是 26 个小写英文字母之一。设 Str(l,r) 表示第 l 杯酒到第 r 杯酒的 r−l+1 个标签顺次连接构成的字符串。若 Str(p,po)=Str(q,qo)，其中 1≤p≤po≤n，1≤q≤qo≤n，p≠q，po−p+1=qo−q+1=r，则称第 p 杯酒与第 q 杯酒是“r相似” 的。当然两杯“r相似” （r>1）的酒同时也是“1 相似”、“2 相似”、…、“(r−1) 相似”的。特别地，对于任意的 1≤p,q≤n，p≠q，第 p 杯酒和第 q 杯酒都是“0相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 i 杯酒 （1≤i≤n） 的美味度为 ai。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 p 杯酒与第 q 杯酒调兑在一起，将得到一杯美味度为 apaq 的酒。现在请各位品酒师分别对于 r=0,1,2,…,n−1，统计出有多少种方法可以选出 2 杯“r相似”的酒,并回答选择 2 杯“r相似”的酒调兑可以得到的美味度的最大值。

做法

分开看这两问。先建出后缀数组。

第一问，可以用单调栈处理出每个height[]height[]覆盖的区间，即预处理出ls[i]ls[i]和rs[i]rs[i]分别表示左右第一个比height[i]height[i]小的位置。扫一遍统计答案。

but对于我们这些蒟蒻。这一问我都不会做。

一开始想的是每个ii对答案的贡献是(i−(ls[i]+1)+1)∗((rs[i]−1)−i+1)−1(i-(ls[i]+1)+1)*((rs[i]-1)-i+1)-1，然而我并没有理解heightheight的含义。

右区间不包含中点。中点与右区间的LCP不是中点的height。 第二问就用一个线段树或者ST表维护区间最大最小值，左右区间的最大最小值依次相乘，最大值肯定在这四个之中。

但是！

我的后缀数组被卡常数了！我还需要怎么优化！罗大神的代码根本看不懂啊！ uoj过了，在BZOJ卡了一上午，换成ST表，各种卡卡卡，都TLE了

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
typedef long long LL;
const int MAXN=300000+100;
const int INF=2e9;
const LL INFXINF=2e18;
char s[MAXN];
int height[MAXN],rnk[MAXN],sa[MAXN];
inline LL max(const LL &a,const LL &b)
{
    return a<b?b:a;
}
inline LL min(const LL &a,const LL &b)
{
    return b<a?b:a;
}
struct Tripple
{
    int a,b,id;
    bool operator <(const Tripple& x)const
    {
        if(a!=x.a)
            return a<x.a;
        return b<x.b;
    }
};
inline bool equal(Tripple *x,Tripple *y)
{
    return x->a==y->a && x->b==y->b;
}
 
void Da(int n)
{
    static Tripple t[MAXN],*p[MAXN],*q[MAXN];
    static int rc[MAXN];
    for(int i=1;i<=n;i++)
        t[i].a=s[i]-'a'+1,t[i].id=i;
    std::sort(t+1,t+1+n);
    for(int i=1,c=0;i<=n;i++)
        rnk[t[i].id]=t[i].a==t[i-1].a?c:++c;
    for(int l=1;l<n;l<<=1)
    {
        for(int i=1;i<=n;i++)
        {
            t[i].a=rnk[i];
            t[i].b=i+l<=n?rnk[i+l]:0;
            t[i].id=i;
            p[i]=&t[i];
        }
        memset(rc,0,sizeof(rc[0])*(n+1));
        for(int i=1;i<=n;i++)
            rc[p[i]->b]++;
        for(int i=1;i<=n;i++)
            rc[i]+=rc[i-1];
        for(int i=n;i;i--)
            q[rc[p[i]->b]--]=p[i];
        memset(rc,0,sizeof(rc[0])*(n+1));
        for(int i=1;i<=n;i++)
            rc[q[i]->a]++;
        for(int i=1;i<=n;i++)
            rc[i]+=rc[i-1];
        for(int i=n;i;i--)
            p[rc[q[i]->a]--]=q[i];
        rnk[p[1]->id]=1;
        for(int i=2,c=1;i<=n;i++)
            rnk[p[i]->id]=equal(p[i],p[i-1])?c:++c;
    }
    for(int i=1;i<=n;i++)
        sa[rnk[i]]=i;
    for(int i=1,j,L=0;i<=n;i++)
    {
        if(rnk[i]!=1)
        {
            j=sa[rnk[i]-1];
            while(s[i+L]==s[j+L])//i+L+1..
                L++;
            height[rnk[i]]=L;
            if(L)
                L--;
        }
    }
}
int ls[MAXN],rs[MAXN],v[MAXN];
void Stack(int n)
{
    height[0]=height[n+1]=-INF;
    ls[1]=0;
    for(int i=2,j;i<=n;i++)
    {
        j=i-1;
        while(height[i]<height[j])
            j=ls[j];
        ls[i]=j;
    }
    rs[n]=n+1;
    for(int i=n-1,j;i;i--)
    {
        j=i+1;
        while(height[i]<=height[j])
            j=rs[j];
        rs[i]=j;
    }
}
struct SegNode
{
    int mx,mn;
    SegNode(int _x=-INF,int _n=INF)
    {
        mx=_x;
        mn=_n;
    }
}seg[MAXN*4];
SegNode operator +(const SegNode &a,const SegNode &b)
{
    return SegNode(max(a.mx,b.mx),min(a.mn,b.mn));
}
void Build(int pos,int L,int R)
{
    if(L==R)
        seg[pos].mx=seg[pos].mn=v[L];
    else
    {
        int MID=(L+R)>>1;
        Build(pos<<1,L,MID);
        Build(pos<<1|1,MID+1,R);
        seg[pos]=seg[pos<<1]+seg[pos<<1|1];
    }
}
LL cnt[MAXN],w[MAXN];
SegNode Access(int pos,int L,int R,int l,int r)
{
    if(L==l && R==r)
        return seg[pos];
    else
    {
        int MID=(L+R)>>1;
        if(r<=MID)
            return Access(pos<<1,L,MID,l,r);
        else if(MID+1<=l)
            return Access(pos<<1|1,MID+1,R,l,r);
        else
            return Access(pos<<1,L,MID,l,MID)+Access(pos<<1|1,MID+1,R,MID+1,r);
    }
}
inline LL Deal(SegNode a,SegNode b)
{
    LL ANS=-INFXINF;
    ANS=max(ANS,(LL)a.mx*b.mx);
    ANS=max(ANS,(LL)a.mn*b.mn);
    // positive
    ANS=max(ANS,(LL)a.mx*b.mn);
    ANS=max(ANS,(LL)a.mn*b.mx);
    // negative   
    return ANS;
}
int main()
{
    //freopen("input.txt","r",stdin);    freopen("ox.txt","w",stdout);
    int n;
    red(n);
    scanf("%s",s+1);
    Da(n);
    Stack(n);
    w[0]=-INFXINF;
    for(int i=1,x;i<=n;i++)
    {
        red(x);
        v[rnk[i]]=x;   
        w[i]=-INFXINF;
    }
    Build(1,1,n);
    for(int i=2,l,r;i<=n;i++)
    {
        cnt[height[i]]+=(LL)(i-ls[i])*(rs[i]-i);
        w[height[i]]=max(w[height[i]],Deal(Access(1,1,n,ls[i],i-1),Access(1,1,n,i,rs[i]-1)));
    }
    for(int i=n-1;~i;i--)cnt[i]+=cnt[i+1],w[i]=max(w[i],w[i+1]);
    for(int i=0;i<n;i++)
        printf("%lld %lld\n",cnt[i],cnt[i]?w[i]:0);
    return 0;
}