UniversalOJ 228 基础数据结构练习题 做题记录

题目链接：UniversalOJ 228 基础数据结构练习题

你需要维护一个数据结构，支持以下三种操作：

• 1 l r k 给 $i\in[l,r]$ 的所有 $a_i$ 加上 $k$；
• 2 l r 对于 $i\in[l,r]$ 的所有 $a_i$，令其变为 $\lfloor\sqrt a_i\rfloor$；
• 3 l r 查询 $\sum\limits_{i=l}^r a_i$；

序列长度为 $n$，操作次数为 $q$，值域为 $V$。

$1\le n,q\le 10^5$，$1\le V\le 10^9$。

不难发现，$\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{\left\lfloor\sqrt{10^9}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor}\right\rfloor=1$，也就是说，值域内一个数变为 $1$ 所需的开根次数可以看作是一个很小的常数。这样若没有区间加操作，我们就可以每次暴力找到区间内非 $1$ 的数，暴力地一个一个处理，这就是 P4145 上帝造题的七分钟 2 / 花神游历各国 的做法。

但是本题有了区间加操作，这使得直接暴力找的时间复杂度退化为 $O(qn)$。但是考虑到因为 $a-b=(\sqrt a - \sqrt b)(\sqrt a+\sqrt b)$，所以开一次根至少会让区间极差变为之前的一半，而当开根退化为区间减的时候就可以快速维护了。

考虑一次区间加对时间复杂度的贡献，由于 $[l,r]$ 操作只会影响到包含 $l$ 和包含 $r$ 的 $O(\log n)$ 个区间，每个区间至多增加 $O(\log V)$，所以时间复杂度为 $O(q\log n\log V)$，足以通过本题。

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int S=100005;

int n,m;
long long a[S];
long long mn[S<<2],mx[S<<2],sm[S<<2],tg[S<<2];

inline void upd(int u)
{
	mn[u]=min(mn[u<<1],mn[u<<1|1]);
	mx[u]=max(mx[u<<1],mx[u<<1|1]);
	sm[u]=sm[u<<1]+sm[u<<1|1];
}

inline void adtg(int u,int l,int r,long long val)
{
	mn[u]+=val;
	mx[u]+=val;
	sm[u]+=val*(r-l+1);
	tg[u]+=val;
}

inline void dwtg(int u,int l,int r)
{
	int mid=l+r>>1;
	adtg(u<<1,l,mid,tg[u]),adtg(u<<1|1,mid+1,r,tg[u]);
	tg[u]=0;
}

void built(int u,int l,int r)
{
	tg[u]=0;
	if(l==r) return mn[u]=mx[u]=sm[u]=a[l],void();
	int mid=l+r>>1;
	built(u<<1,l,mid),built(u<<1|1,mid+1,r);
	upd(u);
}


void add(int u,int l,int r,int L,int R,long long val)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R) return adtg(u,l,r,val);
	dwtg(u,l,r);
	int mid=l+r>>1;
	if(L<=mid) add(u<<1,l,mid,L,R,val);
	if(R>=mid+1) add(u<<1|1,mid+1,r,L,R,val);
	upd(u);
}

void updat(int u,int l,int r,int L,int R)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R)
	{
		long long mnd=mn[u]-(long long)sqrt(mn[u]),mxd=mx[u]-(long long)sqrt(mx[u]);
		if(mnd==mxd) adtg(u,l,r,-mnd);
		else
		{
			dwtg(u,l,r);
			int mid=l+r>>1;
			updat(u<<1,l,mid,L,R),updat(u<<1|1,mid+1,r,L,R);
			upd(u);
		}
		return;
	}
	dwtg(u,l,r);
	int mid=l+r>>1;
	if(L<=mid) updat(u<<1,l,mid,L,R);
	if(R>=mid+1) updat(u<<1|1,mid+1,r,L,R);
	upd(u);
}

long long que(int u,int l,int r,int L,int R)
{
	if(l>R||r<L) return 0;
	if(l>=L&&r<=R) return sm[u];
	dwtg(u,l,r);
	int mid=l+r>>1;
	long long res=0;
	if(L<=mid) res+=que(u<<1,l,mid,L,R);
	if(R>=mid+1) res+=que(u<<1|1,mid+1,r,L,R);
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	built(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			long long v;
			scanf("%lld",&v);
			add(1,1,n,l,r,v);
		}
		else if(op==2) updat(1,1,n,l,r);
		else printf("%lld\n",que(1,1,n,l,r));
	}
	return 0;
}