LOJ6029 [雅礼集训2017]市场

看到区间整除操作，直觉是不会除太多次就变成全 \(1\)。

然而现在还有加操作。

我也不知道为什么，当一个节点的 \(\lfloor\frac{mx}{d}\rfloor=\lfloor\frac{mn}{d}\rfloor\) 的时候变成区间赋值，否则继续递归复杂度是错的，但是 \(\lfloor\frac{mx}{d}\rfloor-mx=\lfloor\frac{mn}{d}\rfloor-mn\) 变成区间加复杂度就对了？？？

下面两个都用上了。

（求证明复杂度……）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=400040;

#define ls o<<1

#define rs o<<1|1

#define lson ls,l,mid

#define rson rs,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

	int x=0,f=0;char ch=getchar();

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,q,a[maxn];

ll sum[maxn],add[maxn],cov[maxn],mx[maxn],mn[maxn];

inline void pushup(int o){

	sum[o]=sum[ls]+sum[rs];

	mx[o]=max(mx[ls],mx[rs]);

	mn[o]=min(mn[ls],mn[rs]);

}

inline void setadd(int o,int l,int r,ll v){

	sum[o]+=(r-l+1)*v;

	mx[o]+=v;

	mn[o]+=v;

	add[o]+=v;

}

inline void setcov(int o,int l,int r,ll v){

	sum[o]=(r-l+1)*v;

	mx[o]=mn[o]=cov[o]=v;

	add[o]=0;

}

inline void pushdown(int o,int l,int r){

	int mid=(l+r)>>1;

	if(cov[o]!=1e18){

		setcov(lson,cov[o]);

		setcov(rson,cov[o]);

		cov[o]=1e18;

	}

	if(add[o]){

		setadd(lson,add[o]);

		setadd(rson,add[o]);

		add[o]=0;

	}

}

void build(int o,int l,int r){

	cov[o]=1e18;

	if(l==r) return void(mx[o]=mn[o]=sum[o]=a[l]);

	int mid=(l+r)>>1;

	build(lson);build(rson);

	pushup(o);

}

void update_add(int o,int l,int r,int ql,int qr,int v){

	if(l>=ql && r<=qr) return setadd(o,l,r,v);

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(mid>=ql) update_add(lson,ql,qr,v);

	if(mid<qr) update_add(rson,ql,qr,v);

	pushup(o);

}

inline ll ddiv(ll x,ll y){

	if(x>=0) return x/y;

	else return -((-x+y-1)/y);

}

void update_div(int o,int l,int r,int ql,int qr,int v){

	if(l>=ql && r<=qr){

		if(ddiv(mx[o],v)==ddiv(mn[o],v)) return setcov(o,l,r,ddiv(mx[o],v));

		if(ddiv(mx[o],v)-mx[o]==ddiv(mn[o],v)-mn[o]) return setadd(o,l,r,ddiv(mx[o],v)-mx[o]);

	}

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(mid>=ql) update_div(lson,ql,qr,v);

	if(mid<qr) update_div(rson,ql,qr,v);

	pushup(o);

}

ll query_sum(int o,int l,int r,int ql,int qr){

	if(l>=ql && r<=qr) return sum[o];

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(mid<ql) return query_sum(rson,ql,qr);

	if(mid>=qr) return query_sum(lson,ql,qr);

	return query_sum(lson,ql,qr)+query_sum(rson,ql,qr);

}

ll query_min(int o,int l,int r,int ql,int qr){

	if(l>=ql && r<=qr) return mn[o];

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(mid<ql) return query_min(rson,ql,qr);

	if(mid>=qr) return query_min(lson,ql,qr);

	return min(query_min(lson,ql,qr),query_min(rson,ql,qr));

}

int main(){

	n=read();q=read();

	FOR(i,1,n) a[i]=read();

	build(1,1,n);

	while(q--){

		int op=read(),l=read()+1,r=read()+1;

		if(op==1) update_add(1,1,n,l,r,read());

		if(op==2) update_div(1,1,n,l,r,read());

		if(op==3) printf("%lld\n",query_min(1,1,n,l,r));

		if(op==4) printf("%lld\n",query_sum(1,1,n,l,r));

	}

}

巴特西

LOJ6029 [雅礼集训2017]市场

最新文章

热门文章