BZOJ 4384 Trzy wieże

Link

好吧,又是神题。。 # Solution 第一步想到了就做出了大半了 设前\(i\)个字符中,有\(b[i]\)个’B’,\(c[i]\)个’C’,\(s[i]\)个’S’ 那么只要有位置\(j\)\(b[i]-b[j]\not=c[i]-c[j]\),\(c[i]-c[j]\not=s[i]-s[j]\),\(b[i]-b[j]\not=s[i]-s[j]\),就可以用\(i-j\)更新答案了 把变量分离出来,得到三元组 \(\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;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利