题解：CF2089B1 Canteen (Easy Version)

· · 题解

赛时做了很一会。

我们考虑我们不是转 a 数组，而是 b 数组，显然就是向左转。

对于一个位置 i，我们考虑 a_i 变为 0 的时刻。

如果 a_i\le b_i，就是 1。

否则我们考虑转的 b_i。

如果是时刻 2，我们要满足 a_i+a_{i+1}\le b_i+b_{i+1}。事实上，通过简单归纳，问题转化为找到最小的 c 满足 \sum_{j=i}^{i+c-1}a_i\le \sum_{j=i}^{i+c-1}b_i，当然因为是环所以稍微处理一下。

然后求所有这样的 c 的最大值即可。

此处的转化容易证明，这里不过多赘述。

我们有个显然的套路就是断环成长度两倍的链，自然做就行。

我们让每个 a_i 减去 b_i。

每个 i 找到最小的 c 使得 \sum_{j=i}^{i+c-1}a_i\le 0，求 c 最大值。

我们可以实时线段树维护对于每个 i 的 c，然后算最大值。

可是我们代码能力太弱了，又懒，怎么办呢？

发现转化后还有个点没用到就是我们求最大值就行。

所以我们可以维护此时的最大值。

考虑以 i 开头所有长度在最大值以内的前缀和。

如果大于 0 就暴力增加答案，往后扩容更多前缀和。

然而，如果答案不变，我们就麻烦了。

当 i 向前一点的时候，所有前缀和都要加一个数，然后加入一个值，但是之前范围内的，现在可能不在范围内。

猛地，我们想到单调队列。

于是每次就是 i 走一格以后如果队头在范围外就删掉。

然后前缀和都加上一个数，计懒标记即可。

然后加入自己。

然后如果队头大于 0，就暴力向后推，如果比队头小就加到队头变成新队头，否则不贡献，知道队头小于 0。

这里的代码把数组翻转，方便思考，所以维护后缀和。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
int a[1000009];
pii q[1000009];
int h=300000,t=299999;
void _main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int b;
        cin>>b;
        a[i]-=b;
    }
    for(int i=n+1;i<=n+n;i++){
        a[i]=a[i-n];
    }
    h=300000,t=299999;
    q[h]={0,-1e16};
    n*=2;
    for(int i=1;i<=n/2;i++){
        swap(a[i],a[n-i+1]);
    }
    int qq;
    qq=0;
    int ma;
    ma=1;
    int hz;
    hz=-1e18;
    a[0]=-1e18;
    for(int i=1;i<=n;i++){
        hz-=a[i-ma];
        hz+=a[i];
        if(h<=t){
            if(q[h].F<=i-ma){
                ++h;
            }
        }
        int aa;
        aa=a[i];
        qq+=aa;
        aa-=qq;
        while(h<=t&&aa<=q[t].S){
            t--;
        }
        q[++t]={i,aa};
        while(q[h].S+qq>0){
            hz+=a[i-ma];
            ma++;
            if(hz-qq<q[h].S){
                q[--h]={i-ma,hz-qq};
            }
        }
    }
    cout<<ma<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        _main();
    }
    return 0;
}