【线段树+均摊思想】UOJ #228 基础数据结构练习题

题面在这里

首先吐槽一下这个题目的名字【大雾

题目意思很简单，但是需要思考的地方很多

主要问题在于如何实现区间开根号

试想：两个不同的数x，y开若干次根号后，必然会趋向于一致：

330 227 → 18 15 → 4 4

那么，在进行若干次操作2后，就有可能得到一段连续的相同值

于是，对于一段相同的序列，区间开根号就等价于区间加

对于不能转化的，就继续把区间分解开来处理

当然，我们还需要注意一种情况：

16 15 → 4 3 → 2 1

即 x=ak,y=x−1 时，两个数的差值不变

代码如下：

void Sqrt(P_node x,int l,int r){
    if (r<x->L||x->R<l) return;
    if (l<=x->L&&x->R<=r)
     if (x->mx==x->mn||x->mx-x->mn==(LL)sqrt(x->mx)-(LL)sqrt(x->mn)){
        LL w=(LL)sqrt(x->mx)-x->mx;
        x->plus(w); return;
     }
    x->pushdown();
    Sqrt(x->l,l,r);Sqrt(x->r,l,r);
    x->pushup();
}
           

下面证明复杂度：

考虑两个差值为V的数，需要开几次根号才能使这两个数一样

开根号=0.5次方：

x1/2、x1/4、x1/8……

设 x2−k=t 其中t<2，则有：

logxt=2−k

log2logxt=−k

log2logtx=k

因为t的取值是 (1,2) 所以我们不妨取 t=2

就可以得到复杂度为 O(loglogV)

那么总复杂度为 O((n+q)logN⋅loglogV)

附上代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=;
int n,q,a[maxn];
struct node{
    node *l,*r;
    int L,R;
    LL mx,mn,s,p;
    node () {}
    node (int x,int y,LL w) {L=x;R=y;mx=mn=s=w;p=;}
    void pushup() {mx=max(l->mx,r->mx);mn=min(l->mn,r->mn);s=l->s+r->s;}
    void plus(LL w) {mx+=w;mn+=w;s+=w*(R-L+);p+=w;}
    void pushdown(){
        if (L==R) return;
        if (p) l->plus(p),r->plus(p),p=;
    }
}nil,base[maxn*];
typedef node* P_node;
P_node null,Rot,len;
void Seg_T_init(){
    nil=node(,,);Rot=null=&nil;
    null->l=null->r=null;len=base;
}
P_node newnode(int x,int y,LL w){
    *len=node(x,y,w);len->l=len->r=null;
    return len++;
}
P_node buildtree(int l,int r){
    P_node x=newnode(l,r,);
    if (l==r) {x->mx=x->mn=x->s=a[l];return x;}
    int mid=l+r>>;
    x->l=buildtree(l,mid);x->r=buildtree(mid+,r);
    x->pushup(); return x;
}
void ist(P_node x,int l,int r,int w){
    if (r<x->L||x->R<l) return;
    if (l<=x->L&&x->R<=r) {x->plus(w);return;}
    x->pushdown();
    ist(x->l,l,r,w);ist(x->r,l,r,w);
    x->pushup();
}
void srt(P_node x,int l,int r){
    if (r<x->L||x->R<l) return;
    if (l<=x->L&&x->R<=r)
     if (x->mx==x->mn||x->mx-x->mn==(LL)sqrt(x->mx)-(LL)sqrt(x->mn)){
        LL w=(LL)sqrt(x->mx)-x->mx;
        x->plus(w); return;
     }
    x->pushdown();
    srt(x->l,l,r);srt(x->r,l,r);
    x->pushup();
}
LL qry(P_node x,int l,int r){
    if (r<x->L||x->R<l) return ;
    if (l<=x->L&&x->R<=r) return x->s;
    x->pushdown();
    return qry(x->l,l,r)+qry(x->r,l,r);
}
inline int red(){
    int tot=,f=;char ch=getchar();
    while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=getchar();}
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    return tot*f;
}
int main(){
    Seg_T_init();
    n=red(),q=red();
    for (int i=;i<=n;i++) a[i]=red();
    Rot=buildtree(,n);
    while (q--){
        int c=red();
        if (c==){
            int l=red(),r=red(),w=red();
            ist(Rot,l,r,w);
        }else
        if (c==){
            int l=red(),r=red();
            srt(Rot,l,r);
        }else{
            int l=red(),r=red();
            printf("%lld\n",qry(Rot,l,r));
        }
    }
    return ;
}