hdu 5828 Rikka with Sequence 线段树

时间:2023-03-08 16:01:18
hdu 5828 Rikka with Sequence 线段树

Rikka with Sequence

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=5828

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

Hint

题意

给你n个数,m个操作

一共有三类操作

区间开根号

区间加

区间求和

题解:

线段树,区间开根号最多十几次就会变成1,我们把相同值的数合并在一起去更新就好了

区间加,就正常做,和普通的线段树一样去做就好了。

区间求和也正常做……

其实就比普通的线段树多一个lazy,表示左右是否相同。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+7;
long long n;
int a[maxn];
int to[2000005];
typedef long long ll;
typedef long long SgTreeDataType; const int BUF=40000000;
char Buf[BUF],*buf=Buf;
const int OUT=20000000;
char Out[OUT],*ou=Out;int Outn[30],Outcnt;
inline void write(int x){
if(!x)*ou++=48;
else{
for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
while(Outcnt)*ou++=Outn[Outcnt--];
}
}
inline void writell(ll x){
if(!x)*ou++=48;
else{
for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
while(Outcnt)*ou++=Outn[Outcnt--];
}
}
inline void writechar(char x){*ou++=x;}
inline void writeln(){*ou++='\n';}
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} inline int TransForm( long long x ){
if( x <= 2000000 ) return to[x];
return sqrt( x );
} struct Sgtree{
struct treenode{
int l , r ;
long long f , lzy , sum ; void Update( long long x ){
lzy += x;
sum += (r - l + 1) * x;
if( ~f ) f += x;
} void SetUp( long long x ){
f = x;
sum = x * ( r - l + 1 );
} void SqrtUp(){
f = TransForm( f );
sum = f * ( r - l + 1 );
} }tree[maxn << 2]; void Push_Up( int o ){
tree[o].sum = tree[o << 1].sum + tree[o << 1 | 1].sum;
if( tree[o << 1].f == tree[o << 1 | 1].f ) tree[o].f = tree[o << 1].f;
else tree[o].f = -1;
} void ReleaseLabel( int o ){
if( tree[o].lzy ){
tree[o << 1].Update( tree[o].lzy );
tree[o << 1 | 1].Update( tree[o].lzy );
tree[o].lzy = 0;
}
if( ~tree[o].f ){
tree[o << 1].SetUp( tree[o].f );
tree[o << 1 | 1].SetUp( tree[o].f );
}
} void Build( int l , int r , int o ){
tree[o].l = l , tree[o].r = r , tree[o].lzy = tree[o].sum = 0;
if( r > l ){
int mid = l + r >> 1;
Build( l , mid , o << 1 );
Build( mid + 1 , r , o << 1 | 1 );
Push_Up( o );
}else tree[o].f = tree[o].sum = a[l];
} void Add( int ql , int qr , int v , int o ){
int l = tree[o].l , r = tree[o].r;
if( ql <= l && r <= qr ) tree[o].Update( v );
else{
int mid = l + r >> 1;
ReleaseLabel( o );
if( ql <= mid ) Add( ql , qr , v , o << 1 );
if( qr > mid ) Add( ql , qr , v , o << 1 | 1 );
Push_Up( o );
}
} void DFS( int o ){
if( ~tree[o].f ){
tree[o].SqrtUp( );
}else{
ReleaseLabel( o );
DFS( o << 1 );
DFS( o << 1 | 1 );
Push_Up( o );
}
} void OpeSqrt( int ql , int qr , int o ){
int l = tree[o].l , r = tree[o].r;
if( ql <= l && r <= qr ) DFS( o );
else{
int mid = l + r >> 1;
ReleaseLabel( o );
if( ql <= mid ) OpeSqrt( ql , qr , o << 1 );
if( qr > mid ) OpeSqrt( ql , qr , o << 1 | 1 );
Push_Up( o );
}
} long long Ask( int ql , int qr , int o ){
int l = tree[o].l , r = tree[o].r;
if( ql <= l && r <= qr ) return tree[o].sum;
else{
int mid = l + r >> 1;
ReleaseLabel( o );
long long Result = 0;
if( ql <= mid ) Result += Ask( ql , qr , o << 1 );
if( qr > mid ) Result += Ask( ql , qr , o << 1 | 1 );
Push_Up( o );
return Result;
}
} }Sgtree; int main()
{
fread(Buf,1,BUF,stdin);
for(int i=0;i<=2000000;i++)
to[i]=sqrt(i);
int t;
read(t);
while(t--){
int n,m;
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
Sgtree.Build( 1 , n , 1 );
while(m--)
{
int op,x,y,z;
read(op),read(x),read(y);
if(op==2) Sgtree.OpeSqrt( x , y , 1 );
if(op==1){
read(z);
Sgtree.Add( x , y , z , 1 );
}
if(op==3)writell(Sgtree.Ask(x,y,1)),writeln();
}
}
fwrite(Out,1,ou-Out,stdout);
return 0;
}