为什么每天都这么晚才回来

· · 题解

提供一个好写的 O(n\log n) 方法。

以下将白格称为空格，黑格称为障碍。

首先我们发现数字要填到空格，就是要我们找两边的障碍。我们可以把格子按每行分开来，然后问题就变成了去找障碍，障碍中间就是空格。这是 O(n^2) 的。但这能给我们一些启示。

把格子并回去，然后考虑能不能单格转移。对于每个点找到左右第一大，中间以这个点为最高格的位置之间都是空格。可能这样说有点抽象，请看例子：

4 3 2 4

那么对于 3，显然能找到左右的 4，然后可以发现，3 与右边的 4 可以构成一个空格，高度为 3，宽度为 1。

但是当搜到 4 时，我们发现了这个解法的一个问题：当数相同时也应记。这个好操作，只要在某一次的单调栈时小改单调的判定就行了。为什么只搜一次呢？我们发现左边的 4 右边第一大是右边的 4，而右边的 4 左边第一大是左边的 4，这样中间高度为 4，宽度为 2 的方格就被重复算了两次。因此搜一次就够。

但是我们发现还存在一个问题。当我们找当前格子高度为多少时，我们不能只看当前格状态，还要看当前格和左右第一大之间（不含）最高的格子是多少，因为我当前的格子算空格肯定不能算在这个区间最高格的。显然可证这个区间第一大比两个端点都小（因为这个如果更大，第一大就不会是更右/更左边的了）。

考虑静态区间求最大值，我们可以使用 rmq 来求。但是我忘记怎么写了，所以写了树状数组。

然后就是最后一个问题，怎么把数放到空格里去。

显然看到这个问题我们会很自然地想到背包。但是时间复杂度爆炸。

然后考虑找性质。我们发现必然放连续空格数最大的优。首先我们考虑，放一个长度为 l 的格子，就会得到 l-1 的收益，我们肯定要让放的个数最小。

当 m\geq l 时，肯定要放这个格子。证明显然。

当 m<l 时，也要放这个格子。证明如下：

假如你去放一个连续的格子 l_2 满足 m<l_2 且 l_2\leq l，那么这与直接放 l 等价。

假如你去放一个连续的格子 l_2 满足 m\geq l_2 且 l_2\leq l，那么这不符合条件“使得放的格子数最小”。

所以我们把格子从大到小处理出来就行。注意到格子值域与 n 同级，所以直接用筒存就行。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int T,n,ans,Max,m,a[maxn],c[maxn],q[maxn],t,l[maxn],r[maxn],cd[maxn];
int lowbit(int x){return x&(-x);}
void modify(int x){
    int y=x;
    while(x<=n){
        c[x]=max(c[x],a[y]);
        x+=lowbit(x);}}
int query(int l,int r){
    int ans=a[r];
    while(l!=r){
        for(--r;r>=l+lowbit(r);r-=lowbit(r))
            ans=max(ans,c[r]);
        ans=max(ans,a[r]);}
    return ans;}
signed main(){
    scanf("%lld",&T);
    while(T--){
        ans=m=Max=0;
        scanf("%lld",&n);
        for(int i=0;i<=n;i++)l[i]=r[i]=c[i]=cd[i]=0;
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]),Max=max(Max,a[i]);
        a[0]=2e15,t=0,q[0]=0;
        for(int i=1;i<=n;i++){
            while(t&&a[q[t]]<=a[i])t--;
            l[i]=q[t];
            q[++t]=i;}
        a[n+1]=2e15,t=0,q[0]=n+1;
        for(int i=n;i>=1;i--){
            while(t&&a[q[t]]<a[i])t--;
            r[i]=q[t];
            q[++t]=i;}
        for(int i=1;i<=n;i++)
            modify(i);
        for(int i=1;i<=n;i++){
            int x=l[i]+1>i-1?0:query(l[i]+1,i-1);
            int y=r[i]-1<i+1?0:query(i+1,r[i]-1);
            cd[i-l[i]-1]+=a[i]-x,cd[r[i]-i-1]+=a[i]-y;}
        cd[n]+=n-Max;
        scanf("%lld",&m);
        for(int i=n;i>=1;i--){
            if(!m)break;
            if(cd[i]){
                if(m>=cd[i]*i){
                    ans+=(i-1)*cd[i];
                    m-=cd[i]*i;}
                else{
                    ans+=(m/i)*(i-1)+max(1ll,m-(m/i)*i)-1;
                    m=0;}}}//这里不能用while暴力枚举每一个cd。因为sigma cd可能大于m，时间复杂度爆炸。
        printf("%lld\n",ans);}
    return 0;}