题目链接:UniversalOJ 228 基础数据结构练习题
你需要维护一个数据结构,支持以下三种操作:
1 l r k
给 的所有 加上 ;2 l r
对于 的所有 ,令其变为 ;3 l r
查询 ;序列长度为 ,操作次数为 ,值域为 。
,。
不难发现,,也就是说,值域内一个数变为 所需的开根次数可以看作是一个很小的常数。这样若没有区间加操作,我们就可以每次暴力找到区间内非 的数,暴力地一个一个处理,这就是 P4145 上帝造题的七分钟 2 / 花神游历各国 的做法。
但是本题有了区间加操作,这使得直接暴力找的时间复杂度退化为 。但是考虑到因为 ,所以开一次根至少会让区间极差变为之前的一半,而当开根退化为区间减的时候就可以快速维护了。
考虑一次区间加对时间复杂度的贡献,由于 操作只会影响到包含 和包含 的 个区间,每个区间至多增加 ,所以时间复杂度为 ,足以通过本题。
代码如下:
#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;
}