题目描述
一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节,分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项,吸引了众多品酒师参加。
在大会的晚餐上,调酒师 Rainbow 调制了杯鸡尾酒。这
杯鸡尾酒排成一行,其中第
杯酒
被贴上了一个标签
,每个标签都是 26 个小写英文字母之一。设
表示第
杯酒到第
杯酒的
个标签顺次连接构成的字符串。若
,其中
,则称第
杯酒与第
杯酒是“
相似” 的。当然两杯“
相似”
的酒同时也是“1相似”、“2相似”、……、“
相似”的。特别地,对于任意的
,第
杯酒和第
杯酒都是“0相似”的。
在品尝环节上,品酒师 Freda 轻松地评定了每一杯酒的美味度,凭借其专业的水准和经验成功夺取了“首席品酒家”的称号,其中第杯酒
的美味度为
。现在 Rainbow 公布了挑战环节的问题:本次大会调制的鸡尾酒有一个特点,如果把第
杯酒与第
杯酒调兑在一起,将得到一杯美味度为
的酒。现在请各位品酒师分别对于
,统计出有多少种方法可以选出 2杯“
相似”的酒,并回答选择 2 杯“
相似”的酒调兑可以得到的美味度的最大值。
输入格式
输入文件的第 1 行包含 1 个正整数 ,表示鸡尾酒的杯数。
第 2 行包含一个长度为 的字符串
,其中第
个字符表示第
杯酒的标签。
第 3 行包含 个整数,相邻整数之间用单个空格隔开,其中第
个整数表示第
杯酒的美味度
。
输出格式
输出文件包括行。第
行输出 2 个整数,中间用单个空格隔开。第 1 个整数表示选出两杯“
相似”的酒的方案数,第 2 个整数表示选出两杯“
相似”的酒调兑可以得到的最大美味度。若不存在两杯“
相似”的酒,这两个数均为 0。
题目解析
NOI的难度真是越来越接近NOIP了。
先解决第一个子问题。题目要求对于每一个,求出有多少对
,满足
。只需要求出
的答案,再求一下后缀和就好。我们先求出
的后缀数组和
数组,有
。可以用单调栈处理一下
向左和向右的影响范围
,则其对答案的贡献为
。这一部分时间复杂度
。
考虑第二个子问题。设的影响范围为左边
,右边
,则问题等价于在
和
中分别选择一个整数,使它们的乘积最大。因为有负数的存在,讨论的情况比较多:
1.若左区间和右区间均有正值,用左区间最大值和右区间的最大值乘积更新答案。
2.若左区间和右区间均有负值,用左区间最小值和右区间的最小值乘积更新答案。
3.若左区间和右区间一侧均为正值,一侧均为负值,用正值区间最小值和负值区间的最大值乘积更新答案。
4.若左区间和右区间有一侧存在零值,用0更新答案。
我们可以维护4棵线段树来实现上述操作。为减小常数,我是用zkw线段树实现的。这一部分时间复杂度。
总时间复杂度。
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 |
/************************************************************** Problem: 4199 User: frank_c1 Language: C++ Result: Accepted Time:7180 ms Memory:54792 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(4e5)+5; const int INF=(int)(1e9)+100; char s[maxn]; int sa[maxn],rk[maxn],ht[maxn]; int c[maxn],x[maxn],y[maxn]; int n; void buildsa() { int k,m=256; REP(i,1,m) c[i]=0; REP(i,1,n) c[x[i]=s[i]]++; REP(i,1,m) c[i]+=c[i-1]; PER(i,n,1) sa[c[x[i]]--]=i; for(k=1;k<=n;k<<=1) { int p=0; REP(i,n-k+1,n) y[++p]=i; REP(i,1,n) if(sa[i]>k) y[++p]=sa[i]-k; REP(i,1,m) c[i]=0; REP(i,1,n) c[x[i]]++; REP(i,1,m) c[i]+=c[i-1]; PER(i,n,1) sa[c[x[y[i]]]--]=y[i]; memcpy(y,x,sizeof(x)); x[sa[1]]=m=1; REP(i,2,n) { if(y[sa[i]]!=y[sa[i-1]] || y[sa[i]+k]!=y[sa[i-1]+k]) ++m; x[sa[i]]=m; } if(m>=n) break; } REP(i,1,n) rk[sa[i]]=i; k=0; REP(i,1,n) { if(k) k--; if(rk[i]==1) continue; int j=sa[rk[i]-1]; while(s[i+k]==s[j+k]) k++; ht[rk[i]]=k; } } int w[maxn]; int stk[maxn],top; int lt[maxn],rt[maxn]; LL rs[maxn],val[maxn]; int P[maxn<<2][2],N[maxn<<2][2],Z[maxn<<2]; int M; inline void modify(int T[][2],int x,int d) { for(x+=M,T[x][0]=T[x][1]=d,x>>=1;x;x>>=1) { T[x][0]=min(T[x<<1][0],T[x<<1|1][0]); T[x][1]=max(T[x<<1][1],T[x<<1|1][1]); } } inline void ins(int x) { for(x+=M,Z[x]=1,x>>=1;x;x>>=1) Z[x]=Z[x<<1]|Z[x<<1|1]; } inline int zero(int s,int t) { int c=0; for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1) { if(~s&1) c|=Z[s^1]; if( t&1) c|=Z[t^1]; } return c; } inline void query(int T[][2],int s,int t,int A[]) { A[0]=INF;A[1]=0; for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1) { if(~s&1) { A[0]=min(A[0],T[s^1][0]); A[1]=max(A[1],T[s^1][1]); } if( t&1) { A[0]=min(A[0],T[t^1][0]); A[1]=max(A[1],T[t^1][1]); } } } int L[2][2],R[2][2]; int main() { read(n); for(M=1;M<=n;M<<=1); scanf("%s",s+1); buildsa(); REP(i,1,M+n) P[i][0]=N[i][0]=INF; REP(i,1,n) { int a; read(a); if(a>0) modify(P,rk[i],a); else if(a<0) modify(N,rk[i],-a); else ins(rk[i]);w[rk[i]]=a; } ht[1]=ht[n+1]=-1; REP(i,0,n-1) val[i]=-1ll*INF*INF; REP(i,2,n+1) { while(top && ht[stk[top]]>ht[i]) rt[stk[top--]-1]=i-1; stk[++top]=i; } PER(i,n,1) { while(top && ht[stk[top]]>=ht[i]) lt[stk[top--]-1]=i; stk[++top]=i; } REP(i,1,n-1) { rs[ht[i+1]]+=1ll*(i-lt[i]+1)*(rt[i]-i); query(P,lt[i],i,L[0]);query(P,i+1,rt[i],R[0]); query(N,lt[i],i,L[1]);query(N,i+1,rt[i],R[1]); LL& res=val[ht[i+1]]; if(L[0][1] && R[0][1]) res=max(res,1ll*L[0][1]*R[0][1]); if(L[1][1] && R[1][1]) res=max(res,1ll*L[1][1]*R[1][1]); if(L[0][0] && R[1][0]) res=max(res,-1ll*L[0][0]*R[1][0]); if(L[1][0] && R[0][0]) res=max(res,-1ll*L[1][0]*R[0][0]); if(zero(lt[i],i) || zero(i+1,rt[i])) res=max(res,0ll); } PER(i,n-2,0) rs[i]+=rs[i+1],val[i]=max(val[i],val[i+1]); REP(i,0,n-1) if(val[i]==-1ll*INF*INF) val[i]=0; REP(i,0,n-1) printf("%lld %lld\n",rs[i],val[i]); return 0; } |