AT_abc256_h [ABC256Ex] I like Query Problem 题解

分析

用势能线段树。

对于一段数字 \(a_l\) 到 \(a_r\)，每次全部除以一个大于 \(1\) 的数，不难发现最多除以 \(\log x\) 次就会使 \(a_l\) 到 \(a_r\) 全部变成 \(0\)，其中 \(x\) 是区间最大值。

所以，在没有操作 \(2\) 的情况下，我们可以在每次操作 \(1\) 的时候都单点修改，只要在某个需要修改的区间 \([l,r]\) 的和为 \(0\) 时，就不对改区间进行操作。但有了操作 \(2\) 之后，数据是可以在每次操作 \(1\) 之后都加 \(1\) 个操作 \(2\)。这样的时间复杂度就退化成 \(O(nq)\) 了。考虑优化。

我们设区间 \([l,r]\) 的势能函数为 \(\mathit{H}(l,r)\)。若 \([l,r]\) 中的权值均相同，则 \(\mathit{H}(l,r)=1\)，否则 \(\mathit{H}(l,r)=\mathit{H}(l,mid)+\mathit{H}(mid+1,r)\)。

在 \([l',r'](l \le l' \le r' \le r)\) 的权值相同的情况下，我们可以直接将 \([l',r']\) 的值全部赋值成 \(\lfloor\frac{v}{x}\rfloor\)，这是能做到 \(O(1)\) 的。其中 \(v\) 是该区间的某一个权值，\(x\) 是操作给的值。否则在 \([l',r'](l \le l' \le r' \le r)\) 的权值不相同的情况下，我们就将操作往下推，分成 \([l',mid],[mid+1,r']\)。对单次区间除法操作的复杂度 \(O(\mathit{H}(l',r'))\)。

总的区间除法的复杂度是 \(O(n \log n \log x)\) 的。

注意 \(1\)：看 \([l,r]\) 的权值是否相同，直接看区间最大和最小值是否相等就行。

注意 \(2\)：区间推平的懒标记初始值是需要赋成 \(-1\) 的，因为存在除法操作之后权值下取整为 \(0\) 的情况。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=2e6+10;
int n,q;
struct node{
	int l,r,mi,ma,lz,s;
}tr[N];
int a[N];

il void up(int now){
	tr[now].s=tr[now<<1].s+tr[now<<1|1].s;
	tr[now].ma=max(tr[now<<1].ma,tr[now<<1|1].ma);
	tr[now].mi=min(tr[now<<1].mi,tr[now<<1|1].mi);
	return ;
}
il void down(int now){
	if(tr[now].lz!=-1){
		tr[now<<1].lz=tr[now].lz,tr[now<<1|1].lz=tr[now].lz;
		tr[now<<1].s=(tr[now<<1].r-tr[now<<1].l+1)*tr[now].lz,tr[now<<1|1].s=(tr[now<<1|1].r-tr[now<<1|1].l+1)*tr[now].lz;
		tr[now<<1].ma=tr[now<<1|1].ma=tr[now].ma;
		tr[now<<1|1].mi=tr[now<<1].mi=tr[now].mi;
		tr[now].lz=-1;
	}
	return ;
}
il void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r,tr[now].lz=-1;
	if(l==r) tr[now].s=tr[now].ma=tr[now].mi=a[l];
	else{
		int mid=l+r>>1;
		build(now<<1,l,mid),build(now<<1|1,mid+1,r);
		up(now);
	}
	return ;
}
il void insert(int now,int l,int r,int x){
	if(tr[now].l>=l&&tr[now].r<=r)
		if(tr[now].ma==tr[now].mi){
			tr[now].ma=tr[now].mi=tr[now].lz=(int)(tr[now].ma/x);
			tr[now].s=(tr[now].r-tr[now].l+1)*tr[now].lz;
			return ;
		}
	down(now);
	int mid=tr[now].l+tr[now].r>>1;	
	if(l<=mid) insert(now<<1,l,r,x);
	if(mid<r) insert(now<<1|1,l,r,x);
	up(now);
	return ;
}
il void insert2(int now,int l,int r,int x){
	if(tr[now].l>=l&&tr[now].r<=r){
		tr[now].ma=tr[now].mi=tr[now].lz=x;
		tr[now].s=(tr[now].r-tr[now].l+1)*tr[now].lz;
	}
	else{
		down(now);
		int mid=tr[now].l+tr[now].r>>1;	
		if(l<=mid) insert2(now<<1,l,r,x);
		if(mid<r) insert2(now<<1|1,l,r,x);
		up(now);
	}
	return ;
}
il int query(int now,int l,int r){
	if(tr[now].l>=l&&tr[now].r<=r) return tr[now].s;
	int ans=0,mid=tr[now].l+tr[now].r>>1;
	down(now);
	if(l<=mid) ans+=query(now<<1,l,r);
	if(mid<r) ans+=query(now<<1|1,l,r);
	up(now);
	return ans;
}

il void solve(){
	cin>>n>>q;
	for(re int i=1;i<=n;++i) cin>>a[i];
	build(1,1,n);
	for(re int i=1,op,l,r,x,y;i<=q;++i){
		cin>>op;
		if(op==1)
			cin>>l>>r>>x,
			insert(1,l,r,x);
		else if(op==2)
			cin>>l>>r>>y,
			insert2(1,l,r,y);
		else
			cin>>l>>r,
			cout<<query(1,l,r)<<"\n";
	}
	return ;
}

signed main(){
	solve();
	return 0;
}