首页 > 代码库 > HDU 5828 Rikka with Sequence(线段树 开根号)
HDU 5828 Rikka with Sequence(线段树 开根号)
Rikka with Sequence
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2777 Accepted Submission(s): 503
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?
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.
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
学军中学
【分析】这个题唯一的难点就是开根号,有两个地方没有想到,想到了就会写了。首先,对于一个数,开根号可以转化成减号,详细肩带吗。其次,对于一个区间,如果最大值==最小值,那么所有的值开完根号都相等了,还有种就就是最大值-最小值==1的时候,可能存在开完根号后差值还是一,这个时候需要特判。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int BufferSize=1<<16; char buffer[BufferSize],*head,*tail; inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++; } inline int read() { 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; } const int N=1e5+1; ll sum[N<<2],lz[N<<2],mx[N<<2],mn[N<<2]; void pushUp(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); mn[rt]=min(mn[rt<<1],mn[rt<<1|1]); } void build(int rt,int l,int r){ lz[rt]=0; if(l==r){sum[rt]=read();mn[rt]=mx[rt]=sum[rt];return;} int mid=l+r>>1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); pushUp(rt); } void pushDown(int rt,int l,int r){ if(lz[rt]!=0){ int mid=l+r>>1; lz[rt<<1]+=lz[rt]; lz[rt<<1|1]+=lz[rt]; mn[rt<<1]+=lz[rt]; mx[rt<<1]+=lz[rt]; mx[rt<<1|1]+=lz[rt]; mn[rt<<1|1]+=lz[rt]; sum[rt<<1]+=lz[rt]*(mid-l+1); sum[rt<<1|1]+=lz[rt]*(r-mid); lz[rt]=0; } } int x,y,t,T,n,m; void sqrtUpdate(int rt,int l,int r){ if(x<=l&&r<=y){ if(mx[rt]==mn[rt]){ lz[rt]-=mx[rt]; mx[rt]=sqrt(mx[rt]); mn[rt]=mx[rt]; lz[rt]+=mx[rt]; sum[rt]=mx[rt]*(r-l+1); return; } else if(mx[rt]==mn[rt]+1){ ll x1=sqrt(mx[rt]); ll x2=sqrt(mn[rt]); if(x1==x2+1){ lz[rt]-=(mx[rt]-x1); sum[rt]-=(mx[rt]-x1)*(r-l+1); mx[rt]=x1;mn[rt]=x2; return; } } } int mid=l+r>>1; pushDown(rt,l,r); if(x<=mid)sqrtUpdate(rt<<1,l,mid); if(y>mid)sqrtUpdate(rt<<1|1,mid+1,r); pushUp(rt); } void addUpdate(int rt,int l,int r){ if(x<=l&&r<=y){ lz[rt]+=t; sum[rt]+=1ll*(r-l+1)*t; mx[rt]+=t;mn[rt]+=t; return ; } int mid=l+r>>1; pushDown(rt,l,r); if(x<=mid)addUpdate(rt<<1,l,mid); if(y>mid)addUpdate(rt<<1|1,mid+1,r); pushUp(rt); } ll query(int rt,int l,int r){ if(x<=l&&r<=y)return sum[rt]; int mid=l+r>>1; pushDown(rt,l,r); ll ret=0; if(x<=mid)ret+=query(rt<<1,l,mid); if(y>mid)ret+=query(rt<<1|1,mid+1,r); return ret; } int main(){ T=read(); while(T--){ n=read();m=read(); build(1,1,n); while(m--){ int op; op=read();x=read();y=read(); if(op==1){ t=read();addUpdate(1,1,n); } else if(op==2)sqrtUpdate(1,1,n); else printf("%I64d\n",query(1,1,n)); } } return 0; }
HDU 5828 Rikka with Sequence(线段树 开根号)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。