题目链接：http://uoj.ac/problem/228
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
正解：线段树
解题报告：
这道题是一道线段树的神题，需要我们支持区间开方、区间加法和区间求和操作。
关键是对于开方操作的处理，考虑如果一个区间最大值等于最小值（即全都相等），那么就可以直接开方，然后区间赋值。
否则就往下递归处理，知道发现整个区间相等再区间操作。
上述做法在这样的数据下会被卡TLE：8、9、8、9，这样每次都会达到最坏复杂度。
但是我们发现他们如果开方之后的减少的值是相同的，也就是说这种情况我们可以特判，变成区间减法操作，这样就可以保证复杂度。
为了降低编程复杂度，可以把区间赋值操作变成区间减法，也就是负数的区间减法，会方便很多。
另外，标记可持久化+不下传，可以大大减小常数。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <complex>
#define lc root<<1
#define rc root<<1|1
using namespace std;
typedef long long LL;
const int MAXN = 100011;
int n,m,c[MAXN],ql,qr,val;
LL ans;
struct node{ int l,r,len; LL sum,Max,Min,tag; }a[MAXN*3];
inline void jia(node &tmp,LL y){ tmp.tag+=y; tmp.Min+=y; tmp.Max+=y; tmp.sum+=tmp.len*y; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void update(int root){
a[root].sum=a[lc].sum+a[rc].sum+a[root].tag*a[root].len;
a[root].Max=max(a[lc].Max,a[rc].Max); a[root].Max+=a[root].tag;
a[root].Min=min(a[lc].Min,a[rc].Min); a[root].Min+=a[root].tag;
}
inline void build(int root,int l,int r){
a[root].l=l; a[root].r=r; a[root].len=r-l+1;
if(l==r) { a[root].Max=a[root].Min=a[root].sum=c[l]; return ; }
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
update(root);
}
inline void add(int root,int l,int r){
if(ql<=l && r<=qr) {
jia(a[root],val);
return ;
}
int mid=(l+r)>>1;
if(ql<=mid) add(root<<1,l,mid);
if(qr>mid) add(root<<1|1,mid+1,r);
update(root);
}
inline void Sqr(int root,int l,int r,LL tag){
if(ql<=l && r<=qr) {
LL cp1,cp2; cp1=(LL)sqrt(a[root].Min+tag)+1; cp2=(LL)sqrt(a[root].Max+tag);//注意比较对象...
LL cha;//long long!!!
if(a[root].Max==a[root].Min){
cha=(a[root].Min+tag)-(LL)sqrt(a[root].Min+tag);
jia(a[root],-cha);
return ;
}
else if((a[root].Max==a[root].Min+1) && cp1==cp2) {//实数相等用eps!!!
cha=(a[root].Min+tag)-(LL)(sqrt(a[root].Min+tag));//没有+1啊...
jia(a[root],-cha);
return ;
}
}
int mid=(l+r)>>1;
if(ql<=mid) Sqr(lc,l,mid,tag+a[root].tag);
if(qr>mid) Sqr(rc,mid+1,r,tag+a[root].tag);
update(root);
}
inline void query(int root,int l,int r,LL tag){
if(ql<=l && r<=qr) {
ans+=a[root].sum+tag*a[root].len;
return ;
}
int mid=(l+r)>>1;
if(ql<=mid) query(lc,l,mid,tag+a[root].tag);
if(qr>mid) query(rc,mid+1,r,tag+a[root].tag);
}
inline void work(){
n=getint(); m=getint(); for(int i=1;i<=n;i++) c[i]=getint();
int type; build(1,1,n);
while(m--) {
type=getint();
if(type==1) {
ql=getint(); qr=getint(); val=getint();
add(1,1,n);
}
else if(type==2) {
ql=getint(); qr=getint();
Sqr(1,1,n,0);
}
else{
ql=getint(); qr=getint(); ans=0;
query(1,1,n,0);
printf("%lld\n",ans);
}
}
}
int main()
{
work();
return 0;
}
原文：http://www.cnblogs.com/ljh2000-jump/p/6357583.html