Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has an array A with n numbers. Then he makes m operations on it.
There are three type of operations:
1 l r x : For each i in [l,r], change A[i] to A[i]+x
2 l r : For each i in [l,r], change A[i] to ⌊√A[i]⌋
3 l r : Yuta wants Rikka to sum up A[i] for all i in [l,r]
It is too difficult for Rikka. Can you help her?
Input
The first line contains a number t(1<=t<=100), the number of the testcases. And there are no more than 5 testcases with n>1000.
For each testcase, the first line contains two numbers n,m(1<=n,m<=100000). The second line contains n numbers A[1]~A[n]. Then m lines follow, each line describe an operation.
It is guaranteed that 1<=A[i],x<=100000.
Output
For each operation of type 3, print a lines contains one number -- the answer of the query.
Sample Input
1
5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5
Sample Output
5
6
题意
实现区间加，区间开根，区间求和
题解
一开始以为可以暴力开根，然后统计区间内是否全为1，后来发现开完根再加又可以开根所以单次复杂度就变成O(n)
后来发现区间开根会出现一大片相同的区域，所以可以再维护一个最大最小值，如果maxx[rt]-minn[rt]==(LL)sqrt(maxx[rt])-(LL)sqrt(minn[rt])||maxx[rt]==minn[rt]就说明区间开根后所有值都相同，那就可以直接更新区间
代码
#include<bits/stdc++.h>
using namespace std; #define LL long long const int maxn=1e5+; LL sum[maxn<<],lazy[maxn<<],minn[maxn<<],maxx[maxn<<]; void pushdown(int l,int r,int rt)
{
if(lazy[rt]==)return;
lazy[rt<<]+=lazy[rt];
lazy[rt<<|]+=lazy[rt];
int mid=(l+r)>>;
sum[rt<<]+=lazy[rt]*(mid-l+);
sum[rt<<|]+=lazy[rt]*(r-mid);
maxx[rt<<]+=lazy[rt];
maxx[rt<<|]+=lazy[rt];
minn[rt<<]+=lazy[rt];
minn[rt<<|]+=lazy[rt];
lazy[rt]=;
}
void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
minn[rt]=min(minn[rt<<],minn[rt<<|]);
maxx[rt]=max(maxx[rt<<],maxx[rt<<|]);
}
void build(int l,int r,int rt)
{
lazy[rt]=;
if(l==r)
{
scanf("%lld",&sum[rt]);
minn[rt]=maxx[rt]=sum[rt];
return;
}
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
void update(int L,int R,LL C,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
lazy[rt]+=C;
sum[rt]+=(r-l+)*C;
maxx[rt]+=C;
minn[rt]+=C;
return;
}
int mid=(l+r)>>;
pushdown(l,r,rt);
if(L<=mid)update(L,R,C,l,mid,rt<<);
if(R>mid)update(L,R,C,mid+,r,rt<<|);
pushup(rt);
}
void Sqrt(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
if(maxx[rt]-minn[rt]==(LL)sqrt(maxx[rt])-(LL)sqrt(minn[rt])||maxx[rt]==minn[rt])
{
LL z=(LL)sqrt(maxx[rt])-maxx[rt];
sum[rt]+=z*(r-l+);
maxx[rt]+=z,minn[rt]+=z,lazy[rt]+=z;
return;
}
}
int mid=(l+r)>>;
pushdown(l,r,rt);
if(L<=mid)Sqrt(L,R,l,mid,rt<<);
if(R>mid)Sqrt(L,R,mid+,r,rt<<|);
pushup(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
return sum[rt];
int mid=(l+r)>>;
LL ans=;
pushdown(l,r,rt);
if(L<=mid)ans+=query(L,R,l,mid,rt<<);
if(R>mid)ans+=query(L,R,mid+,r,rt<<|);
pushup(rt);
return ans;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(,n,);
for(int i=;i<m;i++)
{
int op,l,r;
LL x;
scanf("%d%d%d",&op,&l,&r);
if(op==)
{
scanf("%lld",&x);
update(l,r,x,,n,);
}
else if(op==)
{
Sqrt(l,r,,n,);
}
else if(op==)
{
printf("%lld\n",query(l,r,,n,));
}
}
}
return ;
}
/*
1
5 10
1 2 3 4 5
1 1 3 10
2 1 3
2 1 3
2 1 3
2 1 3
3 1 3
*/