题目链接: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]$$
所以我们可以把此时的区间看作一整块,将除法操作转化为减法(加法)操作。
下面我们对这种情况的渐进时间复杂度进行估计。
考虑最差的情况:
- $n=10^5$;
- $d=2$,这样可以保证分出尽可能多的块,继而尽可能多的分支(递归);
- $a_i$ 的方差尽量大,这样可以保证分出尽可能多的块;
然后发现,这样并不能解决问题。
下面我们引用大佬的势能分析法。
- 当一个区间下取整除了 $\log_2(\max−\min)$ 次后就不需要暴力下取整除,直接区间减即可。
- 定义线段树节点势能为 $\log_2(\max−\min)$,那么每次对 $[l,r]$ 下取整除就是将所有 $l\leq x,y\leq r$,且势能不为 $0$ 的节点 $[x,y]$ 的势能减 $1$ ,代价为势能减少总量。
- 分析区间加操作:只会修改到经过的节点的势能,影响 $\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 – 卢安来的博客。
近期评论