# 【HDU 5828】Rikka with Sequence（线段树）

2016-08-22 09:38:10         来源：ACMer'

Time Limit: 6000/3000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)

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

Author 学军中学
Source 2016 Multi-University Training Contest 8

1 区间加
2 区间开根
3 区间求和

```#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define Pr pair
#define frd(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 112345;
const int mod = 1e9+7;
const double eps = 1e-8;
const int BufferSize=1<<16;
inline char Getchar() {
}
}
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}

LL sum[4*msz],mx[4*msz],mn[4*msz],lz[4*msz];

void down(int root,int l,int r)
{
if(!lz[root]) return;
int mid = (l+r)>>1;
mx[root<<1] += lz[root];
mx[root<<1|1] += lz[root];

mn[root<<1] += lz[root];
mn[root<<1|1] += lz[root];

sum[root<<1] += lz[root]*(mid-l+1);
sum[root<<1|1] += lz[root]*(r-mid);

lz[root<<1] += lz[root];
lz[root<<1|1] += lz[root];
lz[root] = 0;
}

void up(int root)
{
sum[root] = sum[root<<1]+sum[root<<1|1];
mx[root] = max(mx[root<<1],mx[root<<1|1]);
mn[root] = min(mn[root<<1],mn[root<<1|1]);
}

{
if(l == ll && r == rr)
{
return;
}

int mid = (l+r)>>1;

down(root,l,r);

else
{
}

up(root);
}

LL Sum(int root,int l,int r,int ll,int rr)
{
if(l == ll && r == rr)
{
return sum[root];
}

int mid = (l+r)>>1;
down(root,l,r);

if(mid >= rr) return Sum(root<<1,l,mid,ll,rr);
else if(mid+1 <= ll) return Sum(root<<1|1,mid+1,r,ll,rr);
return Sum(root<<1,l,mid,ll,mid)+Sum(root<<1|1,mid+1,r,mid+1,rr);
}

void Sqrt(int root,int l,int r,int ll,int rr)
{
//printf("[%d,%d] mx%lld mn%lld\n",l,r,mx[root],mn[root]);
if(l == ll && r == rr)
{
LL cut;
if(mx[root] == mn[root])
{
cut = mx[root]-floor(sqrt(mx[root]*1.0));
lz[root] -= cut;
sum[root] -= cut*(r-l+1);
mx[root] = mn[root] = mx[root]-cut;
return;
}
else if(mx[root]-mn[root] == 1)
{
LL t1,t2;
t1 = floor(sqrt(mx[root]*1.0));
t2 = floor(sqrt(mn[root]*1.0));
if(t1-t2 == 1)
{
cut = mx[root]-t1;
lz[root] -= cut;
sum[root] -= cut*(r-l+1);
mx[root] = t1;
mn[root] = t2;
return;
}
}
}

int mid = (l+r)>>1;
down(root,l,r);

if(mid >= rr) Sqrt(root<<1,l,mid,ll,rr);
else if(mid+1 <= ll) Sqrt(root<<1|1,mid+1,r,ll,rr);
else
{
Sqrt(root<<1,l,mid,ll,mid);
Sqrt(root<<1|1,mid+1,r,mid+1,rr);
}

up(root);
}

void init(int root,int l,int r)
{
lz[root] = 0;
if(l == r)
{
mx[root] = mn[root] = sum[root];
return;
}

int mid = (l+r)>>1;
init(root<<1,l,mid);
init(root<<1|1,mid+1,r);
up(root);
}

int main()
{
//frd("1008.in");
//fwrite("m.out");

int t,opt,l,r,x,n,q;

while(t--)
{

init(1,1,n);

while(q--)
{
if(opt == 1)
{
}
else if(opt == 2)
{
Sqrt(1,1,n,l,r);
}
else printf("%lld\n",Sum(1,1,n,l,r));
}
}

return 0;
}```