libreoj 6029 「雅礼集训 2017 Day1」市场 题解

题意简述

给定一个长度为 $n\le 10^5$ 的序列，初始值$\le 10^9$，支持：
1 l r x 区间 $[l,r]$ 每个数加上 $x$ 。 $|x|<=10^4,1\le l\le r\le n$
2 l r x 区间 $[l,r]$ 每个数除以 $x$ （下取整），$2\le x\le 1e9,1\le l\le r\le n$
3 l r 求 $[l,r]$ 中的最小值
4 l r 求 $[l,r]$ 的和
询问数 $\le 10^5$

思路

显然线段树。

我们把区间除法分解成区间内每个数都减去某个数。设 $d(a,x)$ 表示 $a$ 除以 $x$ 下取整的变化量，也就是 $a-a/x$。那么 $a\leftarrow a/x$ 的操作，就等价于 $a\leftarrow a-d(a,x)$。显然，当 $x$ 相同的时候， $d$ 函数单调不减。具体的说，如果 $a<b$，则 $d(a,x)\le d(b,x)$ ，对于所有正整数 $x$。

那么对于一段区间，如果 $d(Max,x)=d(Min,x)$，那么这个区间中，所有数的变化量都一样了，直接上区间减法来解决。

否则我们继续把这个区间分成左右两个部分，直到这个区间满足上述条件即可。

分析复杂度

那么这个算法的复杂度是多少呢？看起来每次的最坏情况是暴力的 $O(r-l+1)$ ，但是我们注意到，加法操作中的 $x$ 最大才加 $10000$，但是一次除法操作每次至少除以 $2$。

那比如我是毒瘤出题人，我要卡我的代码，那肯定是要尽量多的加法操作（因为会减慢除法操作），但是也不能少了除法操作（因为看起来很慢）。那假设数据里有 $5\times 10^4$ 个加法操作，还有 $5\times 10^4$ 个除法操作。然后每个数一开始都是 $10^9$ 的规模（不一定恰好是 $10^9$ ，全部相同反而会加快除法操作）。

那加完之后每个数都是 $1.5\times 10^9$ 左右。那么我们把它除个 $31$ 次就全部变成 $0$ 了，那肯定变化量相同，就是能用 $O(log)$ 的减法操作实现了。

那总共就相当于 $O(n \log n \log a)$ ，其中 $a$ 是初始的值域，$\log a$ 大约要到 $32$ 了。

代码 (今天测试一下展开功能)

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class SegmentTree
    {
    public:
        struct node{int l,r,s,m,x,a;}tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define S tree[index].s
        #define M tree[index].m
        #define X tree[index].x
        #define A tree[index].a
        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lS tree[ls].s
        #define lM tree[ls].m
        #define lX tree[ls].x
        #define lA tree[ls].a
        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rS tree[rs].s
        #define rM tree[rs].m
        #define rX tree[rs].x
        #define rA tree[rs].a
        void Update(int index=1)
        {
            S=lS+rS;
            M=min(lM,rM);
            X=max(lX,rX);
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r; A=0;
            if (l==r) {R1(S);M=X=S;return;}
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
            Update(index);
        }
        void AddOne(int x,int index=1)
        {
            A+=x; M+=x; X+=x;
            S+=(R-L+1)*x;
        }
        void PushDown(int index=1)
        {
            if (A)
            {
                AddOne(A,ls); AddOne(A,rs);
                A=0;
            }
        }
        void Add(int l,int r,int x,int index=1)
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return AddOne(x,index);
            PushDown(index);
            Add(l,r,x,ls); Add(l,r,x,rs);
            Update(index);
        }
        int fld(int a,int b)
        {
            int aa=abs(a),bb=abs(b);
            if ((a>0)^(b>0)) return -(aa+bb-1)/bb;
            else return aa/bb;
        }
        void Div(int l,int r,int d,int index=1)
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r)
            {
                int dmax=X-fld(X,d),dmin=M-fld(M,d);
                if (dmax==dmin)
                {
                    AddOne(-dmax,index);
                    return;
                }
            }
            PushDown(index);
            Div(l,r,d,ls); Div(l,r,d,rs);
            Update(index);
        }
        int QueryMin(int l,int r,int index=1)
        {
            if (l>R or L>r) return 0x3f3f3f3f3f3f3f3fll;
            if (l<=L and R<=r) return M;
            PushDown(index);
            return min(QueryMin(l,r,ls),QueryMin(l,r,rs));
        }
        int QuerySum(int l,int r,int index=1)
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S;
            PushDown(index);
            return QuerySum(l,r,ls)+QuerySum(l,r,rs);
        }
    }T;
    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        T.Build(1,n);
    }
    void Soviet()
    {
        F(i,1,m)
        {
            int o,l,r;Rd(3,&o,&l,&r);
            ++l,++r;
            if (o==1)
            {
                int x;R1(x);T.Add(l,r,x);
                // F(i,1,n) printf("%lld ",T.QuerySum(i,i)); putchar('\n'); 
            }
            if (o==2)
            {
                int d;R1(d);T.Div(l,r,d);
                // F(i,1,n) printf("%lld ",T.QuerySum(i,i)); putchar('\n'); 
            }
            if (o==3)
            {
                printf("%lld\n",T.QueryMin(l,r));
            }
            if (o==4)
            {
                printf("%lld\n",T.QuerySum(l,r));
            }
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}