Gym - 101981B Tournament (WQS二分+单调性优化dp)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=3e5+10,inf=0x3f3f3f3f;
 5 int n,m,hd,tl,a[N],q[N],cnt[N],L[N],R[N];
 6 ll S[N],dp[N],k;
 7 ll sum(int l,int r) {return S[r]-S[l-1];}
 8 ll w(int i,int j) {
 9     ++i;
10     return sum((i+j+2)>>1,j)-sum(i,(i+j-1)>>1)+k;
11 }
12 int fd(int j,int k) {
13     int ret=R[k]+1,l=L[k],r=R[k];
14     while(l<=r) {
15         int mid=(l+r)>>1;
16         if(dp[j]+w(j,mid)<=dp[k]+w(k,mid))ret=mid,r=mid-1;
17         else l=mid+1;
18     }
19     return ret;
20 }
21 int solve() {
22     hd=tl=0,L[0]=1,R[0]=n,q[tl++]=0;
23     for(int i=1; i<=n; ++i) {
24         for(; hd<tl&&R[q[hd]]<i; ++hd);
25         dp[i]=dp[q[hd]]+w(q[hd],i);
26         cnt[i]=cnt[q[hd]]+1;
27         for(; hd<tl&&dp[i]+w(i,L[q[tl-1]])<=dp[q[tl-1]]+w(q[tl-1],L[q[tl-1]]); --tl);
28         L[i]=(hd<tl?fd(i,q[tl-1]):i+1),R[i]=n;
29         if(hd<tl)R[q[tl-1]]=L[i]-1;
30         q[tl++]=i;
31     }
32     return cnt[n];
33 }
34 ll bi(ll l,ll r) {
35     ll ret;
36     while(l<=r) {
37         ll mid=(l+r)>>1;
38         k=mid;
39         if(solve()>=m)ret=dp[n]-m*k,l=mid+1;
40         else r=mid-1;
41     }
42     return ret;
43 }
44 int main() {
45     scanf("%d%d",&n,&m);
46     for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
47     for(int i=1; i<=n; ++i)S[i]=S[i-1]+a[i];
48     printf("%lld\n",bi(0,S[n]+10));
49     return 0;
50 }