【loj6092】【雅礼集训 2017 Day1】市场(线段树)

操作1、3、4都是常规操作,我就不讲了。

然后我们考虑怎么处理区间除法。

首先容易想到对于一个数\(x\),它除一次最少除\(2\),那么它最多除\(log_2(x)\)次就会变成\(0\ or\ 1\)。

但是会有区间加法,所以这个东东不可以搞。

于是我们注意到一个性质:

如果:

\[x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor\]

那么有对于所有的\(y\),若\(x\leqslant y \leqslant z\),则有:

\[x-\lfloor\frac{x}{d}\rfloor=y-\lfloor\frac{y}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor\]

证明:

若\(x\leqslant y \leqslant z\),那么

\[\lfloor\frac{x}{d}\rfloor \leqslant \lfloor\frac{y}{d}\rfloor \leqslant \lfloor\frac{z}{d}\rfloor\]且\[\lfloor\frac{y}{d}\rfloor-\lfloor\frac{x}{d}\rfloor \leqslant y-x\]

显而易见

移下项:

\[x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor\]

同理可得:

\[y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor\]

故:

\[x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor\]

所以当

\[x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor\]

时,对于所有的\(x \leqslant y \leqslant z\),都满足:

\[x-\lfloor\frac{x}{d}\rfloor = y-\lfloor\frac{y}{d}\rfloor =z-\lfloor\frac{z}{d}\rfloor\]

得证。

感觉那么一大段字说了一堆废话……

那么每次我们只要判断一下如果这个区间\([l,r]\)的:

\[minn-\lfloor\frac{minn}{d}\rfloor=maxn-\lfloor\frac{maxn}{d}\rfloor\]

由于肯定有\(minn \leqslant a_l,a_{l+1},...,a_r \leqslant maxn\)

所以必有

\[a_l-\lfloor\frac{a_l}{d}\rfloor=a_{l+1}-\lfloor\frac{a_{l+1}}{d}\rfloor=...=a_r-\lfloor\frac{a_r}{d}\rfloor\]

而对于每一个数\(a_i\),\(a_i-\lfloor\frac{a_i}{d}\rfloor\)就是从\(a_i\)变为\(\lfloor\frac{a_i}{d}\rfloor\)需要减多少,所以只要将\(a_i\)减去\(a_i-\lfloor\frac{a_i}{d}\rfloor\),就可以实现除法。

所以这就是一个区间减法,因为每个数都要减去这个值。

所以这一段的代码:

void update2(int k,int l,int r,int ql,int qr,ll val)
{
    int x=floor(1.0*minn[k]/val)-minn[k];
    int y=floor(1.0*maxn[k]/val)-maxn[k];
    if(ql<=l&&r<=qr&&x==y)
    {
        sum[k]+=x*(r-l+1);//区间加(减)
        minn[k]+=x;
        maxn[k]+=x;
        lazy[k]+=x;
        return;
    }
    int mid=(l+r)>>1;
    down(k,l,r,mid);
    if(ql<=mid)update2(k<<1,l,mid,ql,qr,val);
    if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val);
    up(k);
}

时间复杂度:\(O(q\log(n) \log (V))\)。

不会证……

全部代码如下:

#include<bits/stdc++.h>

#define N 100010
#define ll long long
#define LNF 0x7fffffffffffffff

using namespace std;

int n,m,a[N];
ll sum[N<<2],minn[N<<2],maxn[N<<2],lazy[N<<2];

void downn(int k,int l,int r,ll val)
{
    sum[k]+=val*(r-l+1);
    minn[k]+=val;
    maxn[k]+=val;
    lazy[k]+=val;
}

void down(int k,int l,int r,int mid)
{
    if(lazy[k])
    {
        downn(k<<1,l,mid,lazy[k]);
        downn(k<<1|1,mid+1,r,lazy[k]);
        lazy[k]=0;
    }
}

void up(int k)
{
    sum[k]=sum[k<<1]+sum[k<<1|1];
    minn[k]=min(minn[k<<1],minn[k<<1|1]);
    maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}

void build(int k,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&sum[k]);
        maxn[k]=minn[k]=sum[k];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    up(k);
}

void update1(int k,int l,int r,int ql,int qr,ll val)
{
    if(ql<=l&&r<=qr)
    {
        downn(k,l,r,val);
        return;
    }
    int mid=(l+r)>>1;
    down(k,l,r,mid);
    if(ql<=mid)update1(k<<1,l,mid,ql,qr,val);
    if(qr>mid)update1(k<<1|1,mid+1,r,ql,qr,val);
    up(k);
}

void update2(int k,int l,int r,int ql,int qr,ll val)
{
    if(ql<=l&&r<=qr&&floor(1.0*minn[k]/val)-minn[k]==floor(1.0*maxn[k]/val)-maxn[k])
    {
        ll tmp=floor(1.0*minn[k]/val)-minn[k];
        downn(k,l,r,tmp);
        return;
    }
    int mid=(l+r)>>1;
    down(k,l,r,mid);
    if(ql<=mid)update2(k<<1,l,mid,ql,qr,val);
    if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val);
    up(k);
}

ll query1(int k,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
        return minn[k];
    int mid=(l+r)>>1;ll ans=LNF;
    down(k,l,r,mid);
    if(ql<=mid)ans=min(ans,query1(k<<1,l,mid,ql,qr));
    if(qr>mid)ans=min(ans,query1(k<<1|1,mid+1,r,ql,qr));
    return ans;
}

ll query2(int k,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
        return sum[k];
    int mid=(l+r)>>1;ll ans=0;
    down(k,l,r,mid);
    if(ql<=mid)ans+=query2(k<<1,l,mid,ql,qr);
    if(qr>mid)ans+=query2(k<<1|1,mid+1,r,ql,qr);
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        l++,r++;
        if(opt==1)
        {
            ll val;
            scanf("%lld",&val);
            update1(1,1,n,l,r,val);
        }
        if(opt==2)
        {
            ll val;
            scanf("%lld",&val);
            update2(1,1,n,l,r,val);
        }
        if(opt==3)
            printf("%lld\n",query1(1,1,n,l,r));
        if(opt==4)
            printf("%lld\n",query2(1,1,n,l,r));
    }
    return 0;
}
上一篇:某道XJ题


下一篇:[探究] $\mu$函数的性质应用