BZOJ 4384 Trzy wieże

发表于 | 更新于

Link

好吧，又是神题。。

Solution

第一步想到了就做出了大半了 设前ii个字符中，有b[i]b[i]个'B'，c[i]c[i]个'C'，s[i]s[i]个'S' 那么只要有位置jj， , , ，就可以用i−ji-j更新答案了 把变量分离出来，得到三元组 ⟨b[i]−c[i],b[i]−s[i],c[i]−s[i]⟩\langle b[i]-c[i],b[i]-s[i],c[i]-s[i]\rangle 只要保证两个位置的三元组都不相等，就可以了。 第一维排序，第二维树状数组，树状数组维护第三维和位置。 具体说，第一维相同的一起转移，在第二维的树状数组里面维护位置的最大次大和最小次小值，且最值和次值的第三维必须不同，这样就可以查询了。

Tips

对于可以用前缀和维护的量，用上前缀和可能会有奇效

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
#include "lucida"

using std::max;
using std::sort;
using std::pair;
using std::make_pair;
const int MAXN=1000000+11,INF=0x1f1f1f1f;
namespace _Bit_ {
	const int BIT_L=1,BIT_R=-1;
	inline int lowbit(const int &x) {
		return x & -x;
	}
	template <int d> struct Bit {
		int maxv[MAXN<<1][2],minv[MAXN<<1][2],maxi[MAXN<<1],mini[MAXN<<1];
		int n;
		Bit(){}
		Bit(int n):n(n){
			for(int i=1;i<=n;++i) {
				maxv[i][0]=maxv[i][1]=-INF;
				minv[i][0]=minv[i][1]=INF;
			}
		}
		void Modify(int pos,pair<int,int> v) {
			for(;pos && pos<=n;pos+=d*lowbit(pos)) {
				if(v.first>maxv[pos][0]) {
					if(v.second!=maxi[pos])
						maxv[pos][1]=maxv[pos][0];
					maxv[pos][0]=v.first;
					maxi[pos]=v.second;
				} else if(v.first>maxv[pos][1] && v.second!=maxi[pos])
					maxv[pos][1]=v.first;
				if(v.first<minv[pos][0]) {
					if(v.second!=mini[pos])
						minv[pos][1]=minv[pos][0];
					minv[pos][0]=v.first;
					mini[pos]=v.second;
				} else if(v.first<minv[pos][1] && v.second!=mini[pos])
					minv[pos][1]=v.first;
			}
		}
		pair<int,int> Query(int pos,int diff) {
			pair<int,int> res=make_pair(-INF,INF);
			for(;pos && pos<=n;pos-=d*lowbit(pos)) {
				if(maxi[pos]!=diff)
					chkmx(res.first,maxv[pos][0]);
				else
					chkmx(res.first,maxv[pos][1]);
				if(mini[pos]!=diff)
					chkmn(res.second,minv[pos][0]);
				else
					chkmn(res.second,minv[pos][1]);
			}
			return res;
		}
	};
	Bit<BIT_L> pf;Bit<BIT_R> sf;
}using namespace _Bit_;
struct Triple {
	int a,b,c,id;
	Triple(){}
	Triple(int a,int b,int c,int id):a(a),b(b),c(c),id(id){}
	bool operator <(const Triple &x) const {
		return a<x.a;
	}
}node[MAXN];
int main() {
//	freopen("input","r",stdin);
	static char s[MAXN];
	int n;is>>n;
	is>>(s+1);
	int Ans=0;
	int pref[3]={0,0,0};
	for(int i=1,L=0;i<=n;++i) {
		L=(s[i]==s[i-1]?L+1:1);
		chkmx(Ans,L);
		int idx=(s[i]=='B'?0:(s[i]=='C'?1:2));
		pref[idx]++;
		new(&node[i]) Triple(pref[0]-pref[1]+n+1,pref[0]-pref[2]+n+1,pref[1]-pref[2]+n+1,i);
	}
	//因为有0，所以全都偏移了1
	//因为有负数 所以又偏移了n
	int nc=n+1;new(&node[nc]) Triple(n+1,n+1,n+1,0);
	sort(node+1,node+1+nc);
	new (&pf) Bit<BIT_L>((n<<1)+2);
	new (&sf) Bit<BIT_R>((n<<1)+2);
	
	/*
	for(int i=1;i<=nc;++i) {
		#define ir(x) (1<=x && x<=(2*n+1))
		assert(ir(node[i].a));
		assert(ir(node[i].b));
		assert(ir(node[i].c));
	}*/

	for(int l=1,r;l<=nc;l=r+1) {
		for(r=l;node[l].a==node[r+1].a;++r);
		for(int p=l;p<=r;++p) {
			pair<int,int> res;
			res=pf.Query(node[p].b-1,node[p].c);
			chkmx(Ans,max(res.first-node[p].id,node[p].id-res.second));
			res=sf.Query(node[p].b+1,node[p].c);
			chkmx(Ans,max(res.first-node[p].id,node[p].id-res.second));
		}
		for(int p=l;p<=r;++p) {
			pf.Modify(node[p].b,make_pair(node[p].id,node[p].c));
			sf.Modify(node[p].b,make_pair(node[p].id,node[p].c));
		}
	}
	os<<Ans<<'\n';
	return 0;
}