[toc]

题目链接：LibreOJ 6029。

一道特别的线段树题目，非常奇怪的操作，雅礼集训的好题。运用神奇的势能分析法分析算法的时间复杂度，提升自己的姿势水平。

题目

题意简述

一颗线段树，要求支持区间加法、区间除法（向下取整）、区间查询最小值、区间查询和。

题解

思路

首先观察 $1,3,4$ 操作，发现非常简单，用简单的线段树就可以维护，但是看见操作 $2$ 却发现这道题并不是那么简单。

操作 $2$：给定 $l,r,d$，对于 $i\in[l,r],a_i\to\left\lfloor\frac{a_i}{d}\right\rfloor$

然后经过思考，可以发现，如果对于区间 $[l,r]$，如果

$$a_{\max}-\left\lfloor\frac{a_{\max}}{d}\right\rfloor=a_{\min}-\left\lfloor\frac{a_{\min}}{d}\right\rfloor$$

那么

$$\left\lfloor\frac{a_i}{d}\right\rfloor=\left\lfloor\frac{a_{\max}}{d}\right\rfloor=\left\lfloor\frac{a_{\min}}{d}\right\rfloor,i\in[l,r]$$

所以我们可以把此时的区间看作一整块，将除法操作转化为减法（加法）操作。

下面我们对这种情况的渐进时间复杂度进行估计。

考虑最差的情况：

1. $n=10^5$；
2. $d=2$，这样可以保证分出尽可能多的块，继而尽可能多的分支（递归）；
3. $a_i$ 的方差尽量大，这样可以保证分出尽可能多的块；

然后发现，这样并不能解决问题。

下面我们引用大佬的势能分析法。

1. 当一个区间下取整除了 $\log_2(\max−\min)$ 次后就不需要暴力下取整除，直接区间减即可。
2. 定义线段树节点势能为 $\log_2(\max−\min)$，那么每次对 $[l,r]$ 下取整除就是将所有 $l\leq x,y\leq r$，且势能不为 $0$ 的节点 $[x,y]$ 的势能减 $1$ ，代价为势能减少总量。
3. 分析区间加操作：只会修改到经过的节点的势能，影响 $\log_2 a$ 个节点，将这些点的势能恢复为 $\log_2(\max−\min)$。

因此总的时间复杂度就是总势能量 $\Theta((n+m\log_2 n)\log_2 a)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll; //寄存器变量会比较快
typedef unsigned long long ull;
#define INF 0X3F3F3F3F3F3F3F3Fll //定义正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) //fread() 快速读入
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5;
const int MAXQ=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,Q;
ll a[MAXN];

inline void Read(void){
    n=read(),Q=read();
    for(reg int i=1;i<=n;++i)
        a[i]=read();
    return;
}

inline ll Div(reg ll a,reg ll b){ //注意除法的正负性
    if(a<0&&a%b!=0)
        return a/b-1; //负数时记得减掉 1
    else
        return a/b; //正数无需特殊考虑
}

struct SegmentTree{
    #define lson ( (k) << 1 ) //宏定义方便编写
    #define rson ( (k) << 1 | 1) //宏定义方便编写
    #define mid ( ( (l) + (r) ) >> 1 ) //宏定义方便编写
    struct Node{
        ll sum,Max,Min,tag_Add;
        inline Node(reg ll sum=0,reg ll Max=0,reg ll Min=0,reg ll tag_Add=0):sum(sum),Max(Max),Min(Min),tag_Add(tag_Add){
            return;
        }
    };
    Node unit[MAXN<<3];
    inline void pushup(reg int k){
        unit[k]=Node(unit[lson].sum+unit[rson].sum,max(unit[lson].Max,unit[rson].Max),min(unit[lson].Min,unit[rson].Min),0);
        return;
    }
    inline void Add(reg int k,reg int l,reg int r,reg ll val){
        unit[k].sum+=(r-l+1)*val;
        unit[k].Max+=val;
        unit[k].Min+=val;
        unit[k].tag_Add+=val;
        return;
    }
    inline void pushdown(reg int k,reg int l,reg int r){
        if(unit[k].tag_Add){
            Add(lson,l,mid,unit[k].tag_Add);
            Add(rson,mid+1,r,unit[k].tag_Add);
            unit[k].tag_Add=0;
        }
        return;
    }
    inline void Build(reg int k,reg int l,reg int r,reg ll a[]){ //建树
        if(l==r){
            unit[k]=Node(a[l],a[l],a[l],0);
            return;
        }
        Build(lson,l,mid,a);
        Build(rson,mid+1,r,a);
        pushup(k);
        return;
    }
    inline void Update_Add(reg int k,reg int l,reg int r,reg int L,reg int R,reg ll val){ //区间加操作
        if(L<=l&&r<=R){
            Add(k,l,r,val);
            return;
        }
        pushdown(k,l,r);
        if(L<=mid)
            Update_Add(lson,l,mid,L,R,val);
        if(R>mid)
            Update_Add(rson,mid+1,r,L,R,val);
        pushup(k);
        return;
    }
    inline void Update_Div(reg int k,reg int l,reg int r,reg int L,reg int R,reg ll val){ //区间除法操作
        if(L<=l&&r<=R){
            reg ll v1=Div(unit[k].Max,val);
            reg ll v2=Div(unit[k].Min,val);
            if(unit[k].Max-v1==unit[k].Min-v2){ //如果同阶
                reg ll temp=unit[k].Min-v2;
                Add(k,l,r,-temp); //直接化为减法
                return;
            }
        }
        pushdown(k,l,r);
        if(L<=mid)
            Update_Div(lson,l,mid,L,R,val);
        if(R>mid)
            Update_Div(rson,mid+1,r,L,R,val);
        pushup(k);
        return;
    }
    inline ll QueryMin(reg int k,reg int l,reg int r,reg int L,reg int R){ //查询区间最小值
        if(L<=l&&r<=R)
            return unit[k].Min;
        pushdown(k,l,r);
        ll res=INF;
        if(L<=mid)
            res=min(res,QueryMin(lson,l,mid,L,R));
        if(R>mid)
            res=min(res,QueryMin(rson,mid+1,r,L,R));
        return res;
    }
    inline ll QuerySum(reg int k,reg int l,reg int r,reg int L,reg int R){ //查询区间和
        if(L<=l&&r<=R)
            return unit[k].sum;
        pushdown(k,l,r);
        reg ll res=0;
        if(L<=mid)
            res+=QuerySum(lson,l,mid,L,R);
        if(R>mid)
            res+=QuerySum(rson,mid+1,r,L,R);
        return res;
    }
    #undef lson //取消宏定义
    #undef rson //取消宏定义
    #undef mid //取消宏定义
};

SegmentTree T; //线段树变量

inline void Work(void){
    T.Build(1,1,n,a);
    while(Q--){
        static int opt,l,r,val;
        opt=read(),l=read()+1,r=read()+1; //注意下标
        switch(opt){ //用 switch 更快
            case 1:val=read(),T.Update_Add(1,1,n,l,r,val);break;
            case 2:val=read(),T.Update_Div(1,1,n,l,r,val);break;
            case 3:printf("%lld\n",T.QueryMin(1,1,n,l,r));break;
            case 4:printf("%lld\n",T.QuerySum(1,1,n,l,r));break;
            default:break;
        }
    }
    return;
}

这道题的代码比较长，需要耐心，不愧是雅礼集训的一道好题。

更多的线段树题目：线段树 Archives – 卢安来的博客。

回到首页