Mole solution

bh1234666 · 2021-11-08 20:55:55 · 题解

solution Mole

subtask1

纯暴力

10\space pts

subtask2

考虑 dp， dp_{i,j,k} 表示在第 i 位置，前面的 j 个数取了 k 次的答案。

\Theta(n^3)

### subtask3 假设只要求求整个序列的答案。考虑全局贪心。假设我们知道了某种方案某个数取了多少次，且在这个次数下答案最优。显然我们插入合法的最大的可插入的数就可以得到 $\text{次数}+1$的情况下最优的答案。考虑 $\Theta(n)$ 检验某个方案是否可行。设 $C_i$ 表示 $a_i$ 被选的次数，那么对于每一个区间 $[i,i+L-1]$，显然贪心地取最前面 $C_i$ 尚不为零的 $i$。因为先砍后面的前面的可能就砍不到了。使用堆维护序列中最大的(可能)可以插入的最大的数，取出堆顶尝试插入（检验加入后的方案是否可行），若插入失败则显然不可能再次插入，插入成功则将其减一重新入堆（若价值为 $0$ 显然无需再次入堆）。显然最多取 $(t-l+1)$ 个数。考虑维护出全部的答案。假设已知了前 $L$ 段序列的结果（以及维护结束以后的堆），末尾加入的元素显然最多被再取一次，那么更改长度后之前的方案依旧可行且可以通过一次成功的插入操作得到当前的最优方案或者直到堆清空都没有发生插入则之前的方案就是当前的最优方案。维护一个记录当前（可能）可行的数的堆及当前长度最优的方案，每次长度加一尝试进行一次插入即可。 $\Theta(n^2)$，$60\space pts

full task

考虑优化检验到 \Theta(logn)

考虑基于前一次推。对于每一轮检验，设 f_n 为窗口右端到序列右端取的总次数（后缀和），t_n 为窗口右端到 n 至窗口离开序列的时间。

对于一种可行方案，当且仅当 \forall i,f_n\le t_n

充分性证明：假设 f_n>t_n
则在窗口离开之后 a_i(n-L \le i \le n) 中必定有数没取，不合法。

必要性证明：

当其不大于 $t_n$ 并且方案不合法的时候，必定存在$f_x(x<n)>f_n$。考虑 $f$ 的性质，当 $f_n=0$ 时，直接在 $n$ 处扩展一位，即 $f_n=1

（不存在要取的数时直接取走）
否则，f_n←f_n+1，并在下一个位置插入一次取数（相当于顺延直到找到0）

使用线段树维护区间加，并查集~~或线段树二分~~维护某位置后面第一个零。

假设插入一个数之后 f_n>t_n 则无法插入，不合法。

维护存在性，设 d_n=t_n-f_n。

线段树初始化为 t，更新时区间减一，维护区间最小值，判断是否为负数。

考虑任意时间，对当前情况下的时间加一，将最后一位新加入的加进堆，
将 t 的末 L 位加一（末 L 位可以向新的位置移动），在线段树中可以 \Theta(logn)。

由于每次加一处理完后都无法再次插入任何数，因此并查集维护的最后一个零其实就位于当前段末尾。

使用线段树和堆维护即可。

正常维护加一次取数即可，(时间轴上的每次移动最多取数一次)

和上面 subtask3 同理，中途被毙掉的数以后也不会选。

\Theta(nlogn)$，$100\space pts

核心代码:

int n;
struct cmp{
    __attribute__((always_inline)) bool operator () (pair<int,int> a,pair<int,int> b)
    {
        return a.second<b.second;
    }
};
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> q;
int tree[10000005];
int tag[10000005];
void update(int now)
{
    tree[now]+=tag[now];
    tag[(now<<1)]+=tag[now];
    tag[(now<<1)+1]+=tag[now];
    tag[now]=0;
}
bool getmin(int x,int y,int now=1,int f=1,int l=n)//区间是否存在0 
{
    if(f>=x&&l<=y) return tree[now]+tag[now];
    update(now);
    bool fl=1;
    if(((f+l)>>1)+1<=y) fl=getmin(x,y,(now<<1)+1,((f+l)>>1)+1,l);
    if(!fl) return 0;
    if(((f+l)>>1)>=x) fl=getmin(x,y,(now<<1),f,((f+l)>>1));
    return fl;
}
void pls(int num,int x,int y,int now=1,int f=1,int l=n)//区间加 
{
    if(f>=x&&l<=y)
    {
        tag[now]+=num;
        return ;
    }
    update(now);
    if(((f+l)>>1)+1<=y) pls(num,x,y,(now<<1)+1,((f+l)>>1)+1,l);
    if(((f+l)>>1)>=x) pls(num,x,y,(now<<1),f,((f+l)>>1));
    tree[now]=min(tree[(now<<1)]+tag[(now<<1)],tree[(now<<1)+1]+tag[(now<<1)+1]);
}
int main()
{
    input();
    int i;int l;int rd;
    long long ans=0;
    long long pr=0;
    pair<int,int> fl;
    l=read(),n=read();
    for(i=1;i<l;i++)
    {
        rd=read();
        if(rd>0) q.push(pair<int,int>{i,rd});
    }
    for(i=l;i<=n;i++)
    {
        rd=read();
        if(rd>0) q.push(pair<int,int>{i,rd});
        pls(1,i-l+1,i);
        while(!q.empty())
        {
            fl=q.top();
            if(getmin(fl.first,i))
            {
                pls(-1,fl.first,i);
                if(fl.second>0) ans+=fl.second,fl.second--,q.push(fl);;
                q.pop();
                break;
            }
            q.pop();
        }
        write(ans),putchar(' ');
    }
    output();
    return 0;
}