【线段树+势能分析】LOJ6029 「雅礼集训 2017 Day1」市场

题面在这里

​

考虑一个区间除后变化量如果都相同，就转化为区间减了

维护最大值和最小值即可判断

复杂度证明：

考虑两个数\(a,b\)，差是\(a-b\)，除以\(d\)后差是\(\frac{a-b}d\)

也就是说两个数被除\(\log\)次就相等了

令一个线段树节点的势能为\(\log(Max-Min)\)

操作2就相当于把区间内所有势能不为1的节点势能-1，代价为势能减小总量

操作1会将\(\log\)个节点的势能恢复为\(\log(Max-Min)\)

总时间复杂度为整个过程中产生的势能总量\(O((n+q\log n)\log a_i)\)

​

示例程序：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=100005,maxs=400005;
int n,q,a[maxn];
ll mx[maxs],mn[maxs],s[maxs],ad[maxs],len[maxs];
#define ls x<<1
#define rs x<<1|1
inline void pushup(int x) {s[x]=s[ls]+s[rs];mx[x]=max(mx[ls],mx[rs]);mn[x]=min(mn[ls],mn[rs]);}
inline void addad(int x,int w) {mx[x]+=w;mn[x]+=w;ad[x]+=w;s[x]+=len[x]*w;}
inline void pushdown(int x){
	if (ad[x]) addad(ls,ad[x]),addad(rs,ad[x]),ad[x]=0;
}
void build(int x,int l,int r){
	ad[x]=0; len[x]=r-l+1;
	if (l==r) return mx[x]=mn[x]=s[x]=a[l],void();
	int mid=l+r>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	pushup(x);
}
void istad(int x,int l,int r,int ql,int qr,int w){
	if (qr<l||r<ql) return;
	if (ql<=l&&r<=qr) return addad(x,w);
	int mid=l+r>>1; pushdown(x);
	istad(ls,l,mid,ql,qr,w);istad(rs,mid+1,r,ql,qr,w);
	pushup(x);
}
void istdv(int x,int l,int r,int ql,int qr,int d){
	if (qr<l||r<ql) return;
	if (ql<=l&&r<=qr&&floor(1.0*mx[x]/d)-mx[x]==floor(1.0*mn[x]/d)-mn[x]) return addad(x,floor(1.0*mn[x]/d)-mn[x]);
	int mid=l+r>>1; pushdown(x);
	istdv(ls,l,mid,ql,qr,d);istdv(rs,mid+1,r,ql,qr,d);
	pushup(x);
}
ll qrymn(int x,int l,int r,int ql,int qr){
	if (qr<l||r<ql) return 1e18;
	if (ql<=l&&r<=qr) return mn[x];
	int mid=l+r>>1; pushdown(x);
	return min(qrymn(ls,l,mid,ql,qr),qrymn(rs,mid+1,r,ql,qr));
}
ll qrys(int x,int l,int r,int ql,int qr){
	if (qr<l||r<ql) return 0;
	if (ql<=l&&r<=qr) return s[x];
	int mid=l+r>>1; pushdown(x);
	return qrys(ls,l,mid,ql,qr)+qrys(rs,mid+1,r,ql,qr);
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	while (q--){
		int c;scanf("%d",&c);
		if (c==1){
			int l,r,w;scanf("%d%d%d",&l,&r,&w);l++,r++;
			istad(1,1,n,l,r,w);
		}else
		if (c==2){
			int l,r,w;scanf("%d%d%d",&l,&r,&w);l++,r++;
			istdv(1,1,n,l,r,w);
		}else
		if (c==3){
			int l,r;scanf("%d%d",&l,&r);l++,r++;
			printf("%lld\n",qrymn(1,1,n,l,r));
		}else{
			int l,r;scanf("%d%d",&l,&r);l++,r++;
			printf("%lld\n",qrys(1,1,n,l,r));
		}
	}
	return 0;
}