【UOJ228】基础数据结构练习题（线段树）

题面

题解

我们来看看怎么开根？

如果区间所有值都相等怎么办？

显然可以直接开根

如果\(max-sqrt(max)=min-sqrt(min)\)怎么办？

此时意味着虽然开根出来的值不同，但是减去的值相同

举个例子，比如\(8,9\)

开根后是\(2,3\)

虽然值不同，但是差相同

所以，我们把开根换成区间减法

当出现上述两种情况时下放减法标记即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 120000#define lson (now<<1)#define rson (now<<1|1)inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}int n,m,A[MAX];struct Node{ll v,mx,mn,tag;}t[MAX<<2];void Build(int now,int l,int r){ if(l==r){t[now].v=t[now].mx=t[now].mn=A[l];return;} int mid=(l+r)>>1; Build(lson,l,mid);Build(rson,mid+1,r); t[now].v=t[lson].v+t[rson].v; t[now].mx=max(t[lson].mx,t[rson].mx); t[now].mn=min(t[lson].mn,t[rson].mn);}void puttag(int now,int l,int r,ll w){ t[now].v+=w*(r-l+1); t[now].mx+=w;t[now].mn+=w; t[now].tag+=w;}void pushdown(int now,int l,int r){ if(t[now].tag==0)return; int mid=(l+r)>>1; puttag(lson,l,mid,t[now].tag); puttag(rson,mid+1,r,t[now].tag); t[now].tag=0;}void Modify_Plus(int now,int l,int r,int L,int R,int w){ if(L<=l&&r<=R){puttag(now,l,r,w);return;} pushdown(now,l,r); int mid=(l+r)>>1; if(L<=mid)Modify_Plus(lson,l,mid,L,R,w); if(R>mid)Modify_Plus(rson,mid+1,r,L,R,w); t[now].v=t[lson].v+t[rson].v; t[now].mx=max(t[lson].mx,t[rson].mx); t[now].mn=min(t[lson].mn,t[rson].mn);}void Modify_Sqrt(int now,int l,int r,int L,int R){ if(L<=l&&r<=R) { ll a=sqrt(t[now].mx),b=sqrt(t[now].mn); if(t[now].mx==t[now].mn){puttag(now,l,r,a-t[now].mx);return;} if(t[now].mx-a==t[now].mn-b){puttag(now,l,r,a-t[now].mx);return;} } pushdown(now,l,r); int mid=(l+r)>>1; if(L<=mid)Modify_Sqrt(lson,l,mid,L,R); if(R>mid)Modify_Sqrt(rson,mid+1,r,L,R); t[now].v=t[lson].v+t[rson].v; t[now].mx=max(t[lson].mx,t[rson].mx); t[now].mn=min(t[lson].mn,t[rson].mn);}ll Query(int now,int l,int r,int L,int R){ if(L<=l&&r<=R)return t[now].v; pushdown(now,l,r); int mid=(l+r)>>1;ll ret=0; if(L<=mid)ret+=Query(lson,l,mid,L,R); if(R>mid)ret+=Query(rson,mid+1,r,L,R); t[now].v=t[lson].v+t[rson].v; t[now].mx=max(t[lson].mx,t[rson].mx); t[now].mn=min(t[lson].mn,t[rson].mn); return ret;}int main(){ n=read();m=read(); for(int i=1;i<=n;++i)A[i]=read(); Build(1,1,n); while(m--) { int opt=read(),l=read(),r=read(); if(opt==1)Modify_Plus(1,1,n,l,r,read()); else if(opt==2)Modify_Sqrt(1,1,n,l,r); else printf("%lld\n",Query(1,1,n,l,r)); } return 0;}