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

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

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

  • 1 l r ki[l,r]i\in[l,r] 的所有 aia_i 加上 kk
  • 2 l r 对于 i[l,r]i\in[l,r] 的所有 aia_i,令其变为 ai\lfloor\sqrt a_i\rfloor
  • 3 l r 查询 i=lrai\sum\limits_{i=l}^r a_i

序列长度为 nn,操作次数为 qq,值域为 VV

1n,q1051\le n,q\le 10^51V1091\le V\le 10^9

不难发现,109=1\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,也就是说,值域内一个数变为 11 所需的开根次数可以看作是一个很小的常数。这样若没有区间加操作,我们就可以每次暴力找到区间内非 11 的数,暴力地一个一个处理,这就是 P4145 上帝造题的七分钟 2 / 花神游历各国 的做法。

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

考虑一次区间加对时间复杂度的贡献,由于 [l,r][l,r] 操作只会影响到包含 ll 和包含 rrO(logn)O(\log n) 个区间,每个区间至多增加 O(logV)O(\log V),所以时间复杂度为 O(qlognlogV)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;
}