BZOJ 3521 Salad Bar

发表于 | 更新于

Link

Solution

条件等价于选出一个子序列[l,r][l,r]，使得对于 ∀i∈[l,r],count(p)[l,i]≥i−l+12,count(p)[i,r]≥r−i+12\forall i\in [l,r],count(p)[l,i]\ge \dfrac {i-l+1}2,count(p)[i,r]\ge \dfrac {r-i+1}2 然后化简 pref[i]−pref[l−1]≥i−l+12,2pref[i]−i≥2pref[l−1]−(l−1)pref[i]-pref[l-1]\ge \dfrac {i-l+1}2,2pref[i]-i\ge 2pref[l-1]-(l-1) 对于后缀的情况同理 根据这个式子，可以O(nlogn)O(n\log n)地求出以每个点为开头，向左\右延伸，最远的位置lnl,lnrlnl,lnr。 得到了这个之后，问题就转化为 选出一对l,rl,r，使得lnr(l)≥r,lnl(r)≤llnr(l)\ge r,lnl(r)\le l 也可以O(nlogn)O(n\log n)做

看到数据范围和时限，一开始觉得应该是一个很短的纯思路题。在题解的搜索页面上，看到了“树状数组”的字样，才往O(nlogn)O(n\log n)上想。网上的解法都是2O(n)+O(nlogn)2O(n)+O(n\log n)，我的做法是3O(nlogn)3O(n\log n)，感觉很虚。 果然写完之后T了。但是本着n方过百万，卡常出奇迹的心态，开始用gprof卡常。 最后把ST的写法改了一下，更好地利用了cache缓存，然后就A了。

Tips

卡常出奇迹 ST表要写cache友好的版本

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
#include "lucida"
int __a,__b;
#define min(x,y) ( ((__a=(x))<(__b=(y)))?__a:__b )
//using std::min;
int __swap;
#define swap(x,y) (__swap=x,x=y,y=__swap)
using std::reverse;
const int MAXN=1000000+11,MAXLOG=22;

int log_2[MAXN],f[MAXLOG][MAXN];
void ST(int a[],int n) {
	for(int i=1,*fp=&f[0][1];i<=n;++i,++fp)
		*fp=a[i];
	for(int lg=1,endlg=log_2[n];lg<=endlg;++lg)
		for(int i=1,endi=n-(1<<lg)+1,*fp=&f[lg][i],*gp1=&f[lg-1][i],*gp2=&f[lg-1][i+(1<<lg>>1)];i<=endi;++i,++fp,++gp1,++gp2) {//endi=n-(1<<i)+1..
			*fp=min(*gp1,*gp2);
		}
}
int rgmn(int l,int r) {
	if(l>r) swap(l,r);
	int lg=log_2[r-l+1],*fp=f[lg];
	return min(fp[l],fp[r-(1<<lg)+1]);
}
void Calc(int n,char s[],int d[]) {
	static int pref[MAXN];
	for(int i=1;i<=n;++i)
		pref[i]=pref[i-1]+(s[i]=='p');
	for(int i=1;i<=n;++i)
		(pref[i]*=2)-=i;
	//找到最后一个连续的比他大的值
	ST(pref,n);
	for(int i=1;i<=n;++i) {
		int L=i,R=n;
		if(s[i]=='p') {
			while(L!=R) {
				int Mid=(L+R+1)>>1;
				if(rgmn(L,Mid)<pref[i-1]) 
					R=Mid-1;
				else
					L=Mid;
			}
			d[i]=L-i+1;
		} else
			d[i]=1;
	}
}
int main() {
	static char s[MAXN];
	static int pref[MAXN],suf[MAXN];
//	freopen("input","r",stdin);
	int n;is>>n>>(s+1);
	log_2[0]=-1;
	for(int i=1;i<=n;++i)
		log_2[i]=log_2[i>>1]+1;
	int Ans=0;
	Calc(n,s,pref);
	for(int i=1;i<=n;++i)
		pref[i]=i+pref[i]-1;
	reverse(s+1,s+1+n);
	Calc(n,s,suf);
	reverse(suf+1,suf+1+n);
	reverse(s+1,s+1+n);
	for(int i=1;i<=n;++i)
		suf[i]=i-suf[i]+1;
	ST(suf,n);
	for(int i=1;i<=n;++i) {
		if(s[i]=='p') {
			int L=i,R=pref[i];	
			while(L!=R) {	
				int Mid=(L+R+1)>>1;
				if(rgmn(Mid,R)>i)
					R=Mid-1;
				else
					L=Mid;
			}
			chkmx(Ans,L-i+1);
		}
	}
	os<<Ans<<'\n';
	return 0;
}