• 欢迎光临~

【loj6092】【雅礼集训 2017 Day1】市场(线段树)

开发技术 开发技术 2022-10-29 次浏览

操作1、3、4都是常规操作,我就不讲了。

然后我们考虑怎么处理区间除法。

首先容易想到对于一个数(x),它除一次最少除(2),那么它最多除(log_2(x))次就会变成(0 or 1)

但是会有区间加法,所以这个东东不可以搞。

于是我们注意到一个性质:

如果:

[x-lfloorfrac{x}{d}rfloor=z-lfloorfrac{z}{d}rfloor ]

那么有对于所有的(y),若(xleqslant y leqslant z),则有:

[x-lfloorfrac{x}{d}rfloor=y-lfloorfrac{y}{d}rfloor=z-lfloorfrac{z}{d}rfloor ]

证明:

(xleqslant y leqslant z),那么

[lfloorfrac{x}{d}rfloor leqslant lfloorfrac{y}{d}rfloor leqslant lfloorfrac{z}{d}rfloor$$且$$lfloorfrac{y}{d}rfloor-lfloorfrac{x}{d}rfloor leqslant y-x]

显而易见

移下项:

[x-lfloorfrac{x}{d}rfloor leqslant y-lfloorfrac{y}{d}rfloor ]

同理可得:

[y-lfloorfrac{y}{d}rfloor leqslant z-lfloorfrac{z}{d}rfloor ]

故:

[x-lfloorfrac{x}{d}rfloor leqslant y-lfloorfrac{y}{d}rfloor leqslant z-lfloorfrac{z}{d}rfloor]

所以当

[x-lfloorfrac{x}{d}rfloor=z-lfloorfrac{z}{d}rfloor ]

时,对于所有的(x leqslant y leqslant z),都满足:

[x-lfloorfrac{x}{d}rfloor = y-lfloorfrac{y}{d}rfloor =z-lfloorfrac{z}{d}rfloor]

得证。

感觉那么一大段字说了一堆废话……

那么每次我们只要判断一下如果这个区间([l,r])的:

[minn-lfloorfrac{minn}{d}rfloor=maxn-lfloorfrac{maxn}{d}rfloor ]

由于肯定有(minn leqslant a_l,a_{l+1},...,a_r leqslant maxn)

所以必有

[a_l-lfloorfrac{a_l}{d}rfloor=a_{l+1}-lfloorfrac{a_{l+1}}{d}rfloor=...=a_r-lfloorfrac{a_r}{d}rfloor ]

而对于每一个数(a_i)(a_i-lfloorfrac{a_i}{d}rfloor)就是从(a_i)变为(lfloorfrac{a_i}{d}rfloor)需要减多少,所以只要将(a_i)减去(a_i-lfloorfrac{a_i}{d}rfloor),就可以实现除法。

所以这就是一个区间减法,因为每个数都要减去这个值。

所以这一段的代码:

void update2(int k,int l,int r,int ql,int qr,ll val)
{
	int x=floor(1.0*minn[k]/val)-minn[k];
	int y=floor(1.0*maxn[k]/val)-maxn[k];
	if(ql<=l&&r<=qr&&x==y)
	{
		sum[k]+=x*(r-l+1);//区间加(减)
		minn[k]+=x;
		maxn[k]+=x;
		lazy[k]+=x;
		return;
	}
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	if(ql<=mid)update2(k<<1,l,mid,ql,qr,val);
	if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val);
	up(k);
}

时间复杂度:(O(qlog(n) log (V)))

不会证……

全部代码如下:

#include<bits/stdc++.h>

#define N 100010
#define ll long long
#define LNF 0x7fffffffffffffff

using namespace std;

int n,m,a[N];
ll sum[N<<2],minn[N<<2],maxn[N<<2],lazy[N<<2];

void downn(int k,int l,int r,ll val)
{
	sum[k]+=val*(r-l+1);
	minn[k]+=val;
	maxn[k]+=val;
	lazy[k]+=val;
}

void down(int k,int l,int r,int mid)
{
	if(lazy[k])
	{
		downn(k<<1,l,mid,lazy[k]);
		downn(k<<1|1,mid+1,r,lazy[k]);
		lazy[k]=0;
	}
}

void up(int k)
{
	sum[k]=sum[k<<1]+sum[k<<1|1];
	minn[k]=min(minn[k<<1],minn[k<<1|1]);
	maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		scanf("%lld",&sum[k]);
		maxn[k]=minn[k]=sum[k];
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	up(k);
}

void update1(int k,int l,int r,int ql,int qr,ll val)
{
	if(ql<=l&&r<=qr)
	{
		downn(k,l,r,val);
		return;
	}
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	if(ql<=mid)update1(k<<1,l,mid,ql,qr,val);
	if(qr>mid)update1(k<<1|1,mid+1,r,ql,qr,val);
	up(k);
}

void update2(int k,int l,int r,int ql,int qr,ll val)
{
	if(ql<=l&&r<=qr&&floor(1.0*minn[k]/val)-minn[k]==floor(1.0*maxn[k]/val)-maxn[k])
	{
		ll tmp=floor(1.0*minn[k]/val)-minn[k];
		downn(k,l,r,tmp);
		return;
	}
	int mid=(l+r)>>1;
	down(k,l,r,mid);
	if(ql<=mid)update2(k<<1,l,mid,ql,qr,val);
	if(qr>mid)update2(k<<1|1,mid+1,r,ql,qr,val);
	up(k);
}

ll query1(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
		return minn[k];
	int mid=(l+r)>>1;ll ans=LNF;
	down(k,l,r,mid);
	if(ql<=mid)ans=min(ans,query1(k<<1,l,mid,ql,qr));
	if(qr>mid)ans=min(ans,query1(k<<1|1,mid+1,r,ql,qr));
	return ans;
}

ll query2(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
		return sum[k];
	int mid=(l+r)>>1;ll ans=0;
	down(k,l,r,mid);
	if(ql<=mid)ans+=query2(k<<1,l,mid,ql,qr);
	if(qr>mid)ans+=query2(k<<1|1,mid+1,r,ql,qr);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--)
	{
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		l++,r++;
		if(opt==1)
		{
			ll val;
			scanf("%lld",&val);
			update1(1,1,n,l,r,val);
		}
		if(opt==2)
		{
			ll val;
			scanf("%lld",&val);
			update2(1,1,n,l,r,val);
		}
		if(opt==3)
			printf("%lldn",query1(1,1,n,l,r));
		if(opt==4)
			printf("%lldn",query2(1,1,n,l,r));
	}
	return 0;
}
程序员灯塔
转载请注明原文链接:【loj6092】【雅礼集训 2017 Day1】市场(线段树)
喜欢 (0)