【loj6092】【雅禮集訓 2017 Day1】市場（線段樹）

操作1、3、4都是正常操作，我就不講了。

然後我們考慮怎麼處理區間除法。

首先容易想到對于一個數 x x x，它除一次最少除 2 2 2，那麼它最多除 l o g 2 ( x ) log_2(x) log2​(x)次就會變成 0   o r   1 0\ or\ 1 0 or 1。

但是會有區間加法，是以這個東東不可以搞。

于是我們注意到一個性質：

如果：

x − ⌊ x d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx​⌋=z−⌊dz​⌋

那麼有對于所有的 y y y，若 x ⩽ y ⩽ z x\leqslant y \leqslant z x⩽y⩽z，則有：

x − ⌊ x d ⌋ = y − ⌊ y d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=y-\lfloor\frac{y}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx​⌋=y−⌊dy​⌋=z−⌊dz​⌋

證明：

若 x ⩽ y ⩽ z x\leqslant y \leqslant z x⩽y⩽z,那麼

⌊ x d ⌋ ⩽ ⌊ y d ⌋ ⩽ ⌊ z d ⌋ \lfloor\frac{x}{d}\rfloor \leqslant \lfloor\frac{y}{d}\rfloor \leqslant \lfloor\frac{z}{d}\rfloor ⌊dx​⌋⩽⌊dy​⌋⩽⌊dz​⌋且 ⌊ y d ⌋ − ⌊ x d ⌋ ⩽ y − x \lfloor\frac{y}{d}\rfloor-\lfloor\frac{x}{d}\rfloor \leqslant y-x ⌊dy​⌋−⌊dx​⌋⩽y−x

顯而易見

移下項：

x − ⌊ x d ⌋ ⩽ y − ⌊ y d ⌋ x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor x−⌊dx​⌋⩽y−⌊dy​⌋

同理可得：

y − ⌊ y d ⌋ ⩽ z − ⌊ z d ⌋ y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor y−⌊dy​⌋⩽z−⌊dz​⌋

故：

x − ⌊ x d ⌋ ⩽ y − ⌊ y d ⌋ ⩽ z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor \leqslant y-\lfloor\frac{y}{d}\rfloor \leqslant z-\lfloor\frac{z}{d}\rfloor x−⌊dx​⌋⩽y−⌊dy​⌋⩽z−⌊dz​⌋

是以當

x − ⌊ x d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor=z-\lfloor\frac{z}{d}\rfloor x−⌊dx​⌋=z−⌊dz​⌋

時，對于所有的 x ⩽ y ⩽ z x \leqslant y \leqslant z x⩽y⩽z，都滿足：

x − ⌊ x d ⌋ = y − ⌊ y d ⌋ = z − ⌊ z d ⌋ x-\lfloor\frac{x}{d}\rfloor = y-\lfloor\frac{y}{d}\rfloor =z-\lfloor\frac{z}{d}\rfloor x−⌊dx​⌋=y−⌊dy​⌋=z−⌊dz​⌋

得證。

感覺那麼一大段字說了一堆廢話……

那麼每次我們隻要判斷一下如果這個區間 [ l , r ] [l,r] [l,r]的：

m i n n − ⌊ m i n n d ⌋ = m a x n − ⌊ m a x n d ⌋ minn-\lfloor\frac{minn}{d}\rfloor=maxn-\lfloor\frac{maxn}{d}\rfloor minn−⌊dminn​⌋=maxn−⌊dmaxn​⌋

由于肯定有 m i n n ⩽ a l , a l + 1 , . . . , a r ⩽ m a x n minn \leqslant a_l,a_{l+1},...,a_r \leqslant maxn minn⩽al​,al+1​,...,ar​⩽maxn

是以必有

a l − ⌊ a l d ⌋ = a l + 1 − ⌊ a l + 1 d ⌋ = . . . = a r − ⌊ a r d ⌋ a_l-\lfloor\frac{a_l}{d}\rfloor=a_{l+1}-\lfloor\frac{a_{l+1}}{d}\rfloor=...=a_r-\lfloor\frac{a_r}{d}\rfloor al​−⌊dal​​⌋=al+1​−⌊dal+1​​⌋=...=ar​−⌊dar​​⌋

而對于每一個數 a i a_i ai​， a i − ⌊ a i d ⌋ a_i-\lfloor\frac{a_i}{d}\rfloor ai​−⌊dai​​⌋就是從 a i a_i ai​變為 ⌊ a i d ⌋ \lfloor\frac{a_i}{d}\rfloor ⌊dai​​⌋需要減多少，是以隻要将 a i a_i ai​減去 a i − ⌊ a i d ⌋ a_i-\lfloor\frac{a_i}{d}\rfloor ai​−⌊dai​​⌋，就可以實作除法。

是以這就是一個區間減法，因為每個數都要減去這個值。

是以這一段的代碼：

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 ( q log ⁡ ( n ) log ⁡ ( V ) ) O(q\log(n) \log (V)) 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("%lld\n",query1(1,1,n,l,r));
		if(opt==4)
			printf("%lld\n",query2(1,1,n,l,r));
	}
	return 0;
}