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;
}