CF671E Organizing a Race

link

网上大多数都是$O(n\log^2 n)$的,不过我做法是$O(n\log n)$的…

题解

首先考虑没有$k$限制的情况(或者说加完之后)如何判断$l,r$是否可以办比赛。

将题意中的$g_i$用$a_i$表示,$w_i$用$b_i$表示。

设$f_n=f_{n-1}+(a_{i-1}-b_{i-1}),g_n=g_{n-1}+b_{i-1}-a_i$。

那么$l,r$可以办比赛当且仅当
$$f_l=\min _{l\leq i \leq r} f_i,g_r=\min _{l\leq i \leq r} g_i$$

那么考虑有$k$限制的情况。

如果$a_i+1$,那么对于$i\lt j,f_j=f_j+1$,对于$i\le j,g_j=g_j-1$

从$n$到$1$枚举$l$,设单调栈为$f_l\gt f_{x_1}\gt f_{x_2}\gt f_{x_3}\ldots(l\lt x_1\lt x_2\lt x_3\ldots)$

那么为了$l$到$r$满足条件,肯定是$a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}$对于i升序一个一个执行直到$l$能到$r$,其中$x_0=l$

接下来考虑$r$到$l$。

设$h_i$为做完$a_{x_i-1}=a_{x_i-1}+f_{x_{i-1}}-f_{x_i}$后的$g_i$,

显然剩下的$a_i$增加都要给$a_r$,那么$r$能到$l$当且仅当$g_r-k\leq h_i,l\le i\lt r$

如果对于$i\le l$定义$h_i=\infty$,那么就是$g_r-k\leq h_i,i\lt r$

可以在单调栈二分出$r$的上界,然后在线段树上二分得到最大可行$r$。

时间复杂度$O(n\log n)$。

代码

define int long long

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
int a[100005],b[100005],f[100005],g[100005];
int s[100005],t;
int n,k;
struct smt{
int amn,bmn,atg;
int ls,rs;
smt *l,*r;
smt(int la,int ra){
amn=inf;bmn=-inf;
atg=0;
ls=la;rs=ra;
if(ls==rs){
l=r=0;
}
else{
int mid=(ls+rs)>>1;
l=new smt(ls,mid);
r=new smt(mid+1,rs);
}
}
void setg(int x){
if(ls==rs){
amn=bmn=g[x];
return;
}
if(x<=l->rs)l->setg(x);
else r->setg(x);
amn=min(l->amn,r->amn);
bmn=min(l->bmn,r->bmn);
}
void push_down(){
l->atg+=atg;
l->amn+=atg;
r->atg+=atg;
r->amn+=atg;
atg=0;
}
void add(int la,int ra,int w){
if(la<=ls && rs<=ra){
atg+=w;amn+=w;
return;
}
push_down();
if(la<=l->rs)l->add(la,ra,w);
if(ra>=r->ls)r->add(la,ra,w);
amn=min(l->amn,r->amn);
}
int query(int x,int rm){
if(ls>rm)return 0;
if(ls==rs)return ls;
push_down();
if(min(x,l->amn)>=r->bmn-k){
int ans=r->query(min(x,l->amn),rm);
if(ans)return ans;
}
return l->query(x,rm);
}
};
smt *rt;
signed main(){
#ifdef QAQAutoMaton
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
#endif
read(n,k);
rt=new smt(1,n);
for(int i=1;i<n;++i)read(b[i]);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i){
f[i]=f[i-1]+a[i-1]-b[i-1];
}
for(int i=1;i<=n;++i){
g[i]=g[i-1]+b[i-1]-a[i];
}
int ans=0;
for(int i=n;i;--i){
rt->setg(i);
while(t && f[s[t]]>=f[i]){
if(t>1){
rt->add(s[t-1]-1,n,f[s[t]]-f[s[t-1]]);
}
--t;
}
s[++t]=i;
if(t>1){
rt->add(s[t-1]-1,n,f[s[t-1]]-f[s[t]]);
}

s[0]=n+1;

int l=1,r=t,mid;
while(l<=r){
mid=(l+r)>>1;
if(f[i]-f[s[mid]]<=k)r=mid-1;
else l=mid+1;
}
chkmax(ans,rt->query(inf,s[r]-1)-i+1);
}
write(ans,'\n');
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×