[Ynoi2013]对数据结构的爱

\(\texttt {data-2020-9-17}\)

修正了一些公式和语言描述上的错误。


本文中的取模均指减 \(p\)。

很明显前面的值会影响到后面的运算,第一直觉需要处理前缀和,但这个前缀和是否需要取模呢?

\(\operatorname A:\) 预处理不进行取模操作。

也就是说这里维护的是真正意义上的前缀和。

感觉难以构建,原因是:同一个块内,某个位置是否需要取模同时还取决于前面维护的那个 \(sum\) 的值。

对于当前要处理的块 \(x\),若给定不同的 \(sum\) ,其模 \(p\) 的次数 \(k\) 也不同,那么 \(k\) 和 \(sum\) 是否满足什么关系呢?

意淫一下感觉是非递减,看能不能写清楚。

考虑增大 \(sum\) ,此时虽然模 \(p\) 的位置并不确定,但是 \(k\) 要么不变,要么增大,理解一下这个过程中取模位置和次数的变化:

先扫过去,对于 \(i\in[l_1,r_1)\) 这段范围内的数,过程量 \(sum_i\) 都增加 \(num\)(增大的量),原来满足 \(sum_i<p\) 这个条件的有:\(sum_i+num<p\)。

然后 \(r_1\) 这个位置满足:\(sum_{r_1}<p\) 且 \(sum_{r_1}+num\ge p\),此时 \(r_1\) 这个位置取模。

这时有两种情况:

\(1.\ num-p\ge 0\)

对于 \(i\in[r_1,r_2)\) 这段范围内的数,过程量 \(sum_i\) 都增加 \(num-p\),后同上。

\(2.\ num-p<0\)

实际上这个子问题就是 \(num<0\) 的实现。

此时后面一段的过程量减小,直到一个原本取模的位置不取模了,而这个情况可以看做两个位置是否取模的真假(true or false)交换,然后后面的又是变成跟原来一样的子问题。但也有可能后面没有这个真变假(原本取模变成不取模)的位置。

综上可得:对于每个使 \(k+1\) (对 \(k\) 产生了 \(1\) 的贡献)的位置,最多有一个使 \(k-1\) 的位置与其对应,所以 \(k\) 随 \(sum\) 非严格单调递增。

接下去就是考虑实现了:

\(k\) 随 \(sum\) 非严格单调递增,同时有 \(0\le k\le lens\),其中 \(lens\) 为块长。

更严格来说,设原来的取模次数为 \(sl\),有:

\[\begin {cases} sl\le k\le lens,sum>0\\ 0\le k\le sl,sum<0\end {cases} \]

这里 \(k\) 和 \(sum\) 的关系十分相似于函数 \(y=\left\lfloor x \right\rfloor\)。

那么如果二分 \(sum\) 的话,扫过这个块模拟,就可以得到这个 \(sum\) 对应的 \(k\)。

也就是说可以预处理出对于每个 \(k\),最小的 \(sum\) 值,设这个东西为 \(f(k)\),特殊的,\(f(0)=-\infty\)。

那么如果前面的值处理好了传给当前区间,就可以求出对应的 \(k\) 然后加上这段区间的和,减去取模次数乘模数。

(那么 \(\operatorname B:\) 不取模就不用考虑了)

分块的话:

预处理复杂度:\(\operatorname O(\log(2e9\times lens)\times n)\) 乘上一个常数。

查询的复杂度:\(\operatorname O(m\times \frac{n}{lens}\times \log lens)\)

最优的极限复杂度为:\(1.3\times 10^{10}\)。


分块打了,炸了

看了题解,不是傻傻的块里面又重新算,而是“合并”左右子树的信息。

处理好自己左子树和右子树的信息以后,设当前节点为 \(i\),左儿子为 \(l\),右儿子为 \(r\)。

\[f_{i,x+y}=\min(f_{i,x+y},\max(f_{l,x},f_{r,y}+p\times x-add_l) \]

其中,\(add_l\) 表示 \(l\) 这段区间的和,\(x,y\) 分别为左右区间取模的次数。

关于@81179332_ 提到的 \(c_{x+1}-c_x\ge p\) 的证明(在我这里写成 \(f_{x+1}-f_x\ge p\)),我的理解是:

因为 \(f_x\) 对应的是取模 \(x\) 次 \(sum\) 的最小值,那么当 \(sum=f_x-1\),有一个本来要取模的位置不取模了,所以只可能是某个过程量在 \(sum=f_x\) 的时候刚好等于 \(0\)(即这步操作减 \(p\) 以后等于 \(0\))。

当 \(sum=f_x+p-1\) 时,可以用前面 \(\operatorname A\) 的处理过程结合上一段来理解,\(k\) 一定等于 \(x\),所以相邻两个值的差至少为 \(p\)。


那么对于上面的式子来说,有:

\[\begin {cases}f_{r,y}+p\times x-add_l\ge f_{r,y-1}+ p\times (x+1)-add_l \\ f_{l,x}+p\le f_{l,x+1}\end {cases} \]

并且一个合法的二元组 \((x,y)\) 需满足:\(f_{l,x+1}-1+add_l-p\times x\ge f_{r,y}\)

对于一个常数 \(k=x+y\),若 \(k\) 已经被 \((x,y)\) 更新过了,那么 \((x+1,y-1)\) 还有存在的必要吗?

由前面可以得到:

\[f_{r,y-1}+p\times x-add_l\le f_{r,y}+p\times x-add_l\le f_{l,x+1}-1 \]

那么此时对于二元组 \((x+1,y-1)\),\(\max(f_{l,x+1},f_{r,y-1}+p\times x-add_l)\) 取得一定是前面的那项。

前面那项和 \(y\) 又没有任何关系,所以有:

如果存在合法二元组 \((x,y)\),则 \((x+1,y-1)\) 对答案无贡献。(当然,要考虑 \(x\) 的贡献。即如果 \((x,|r|)\) 符合二元组,为了让 \(x+1\) 的贡献能够更新 \(f_{i,x+|r|+1}\),之后 \((x+1,|r|)\) 也得考虑)

注:这里的 \(|r|\) 指区间 \(r\) 的长度,即 \(y\) 的最大取值。

那么就可以双指针使得复杂度正确了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAN=1e6+3;
const LL MAX=1e18;
struct milk
{
    int l,r;
    int ls,rs;
    int lens;
    LL sum;
    vector <long long> q;
}t[MAN<<1];
int nam;
int n,m;
LL ans=0;
LL p;
int rin()
{
    int s=0;
    char c=getchar();
    bool bj=0;
    for(;(c>'9'||c<'0')&&c!='-';c=getchar());
    if(c=='-')c=getchar(),bj=true;
    for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
    if(bj)return -s;
    return s;
}
inline void make_tree(int l,int r,int i)
{
    t[i].l=l;t[i].r=r;
    t[i].lens=t[i].r-t[i].l+1;
    t[i].ls=t[i].rs=0;
    t[i].q.push_back(-MAX);//f[0]为负无穷
    if(l==r)
    {
        t[i].sum=rin();
        t[i].q.push_back(p-t[i].sum);
        t[i].q.push_back(MAX);
        return;
    }
    int mid=(l+r)>>1;
    t[i].ls=++nam;make_tree(l,mid,nam);
    t[i].rs=++nam;make_tree(mid+1,r,nam);
    t[i].sum=t[t[i].ls].sum+t[t[i].rs].sum;
    for(int _=l;_<=r+3;_++)t[i].q.push_back(MAX);
    l=t[i].ls;r=t[i].rs;
    int x,y;
    x=y=0;
    for(;x<=t[l].lens;x++)
    {
        if(y>t[r].lens)y--;
        for(;y<=t[r].lens;y++)
        {
            if(t[l].q[x+1]-1-p*x+t[l].sum<t[r].q[y]){if(y!=0)y--;break;}//当前的 x 无法满足后面减 y 次的需求
            t[i].q[x+y]=min(t[i].q[x+y],max(t[l].q[x],t[r].q[y]+p*x-t[l].sum));
        }
    }
    return;
}
inline void cheak(int l,int r,int i)
{
    if(l<=t[i].l&&t[i].r<=r)
    {
        int left=1,right=t[i].r-t[i].l+1;
        int last=0;
        for(;left<=right;)
        {
            int mid=(left+right)>>1;
            if(ans>=t[i].q[mid])last=mid,left=mid+1;
            else right=mid-1;
        }
        ans+=t[i].sum;
        ans-=p*last;
        return;
    }
    if(t[i].ls==0)return;
    if(t[t[i].ls].r>=l)cheak(l,r,t[i].ls);
    if(t[t[i].rs].l<=r)cheak(l,r,t[i].rs);
    return;
}
int main()
{
    int i,j;
    n=rin();m=rin();p=rin();
    nam=1;
    make_tree(1,n,1);
    for(i=1;i<=m;i++)
    {
        int l,r;
        l=rin();r=rin();
        ans=0;
        cheak(l,r,1);
        printf("%lld\n",ans);
    }
    return 0;
}
上一篇:黑马程序员----java基础笔记下(毕向东)


下一篇:Python习题集(十四)