【UOJ#228】基础数据结构练习题 线段树

#228. 基础数据结构练习题

题目链接：http://uoj.ac/problem/228

Solution

这题由于有区间+操作，所以和花神还是不一样的。 花神那道题，我们可以考虑每个数最多开根几次就会成1，而这个必须利用开根的性质

我们维护区间最大、最小、和。区间加操作可以直接做。

区间开方操作需要特殊考虑。

首先对于一个区间，如果这个区间的所有数取$x=\left \lfloor \sqrt{x} \right \rfloor$值一样，那么就可以直接区间覆盖。

分析上述过程，一个区间可以直接覆盖，当这个区间的差值满足一个特定的范围。 而每次开方这个差值就会减少，可以证明这样开方$lg^{2}$次就会全部为1

所以剩下的我们就可递归下去。

这样的话，区间+操作，就相当于重置了这个差值，所以复杂度还是科学的。

但是有一种情况出现问题。

上述是每次开方后，差值减小，但是有开方后差值不变的情况。  例如 3 4 3 4 3 4 3 4

即$a$,$b$当$b$为完全平方数，$a=b-1$时。这样开方完差值还是1，然后区间+2就又变回来了。 这样上述就卡成了暴力。

那么我们把这种情况特殊考虑。 这样可以转化为一个区间－的操作。剩下的暴力递归，这样就可以了。

时间复杂度是$O(NlogNlg^2{N})$

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

inline int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 100010

int N,M,a[MAXN];

namespace SegmentTree

{

    struct SegmentTreeNode{int l,r,cov; LL tag,sum,maxx,minx;}tree[MAXN<<];

    #define ls now<<1

    #define rs now<<1|1

    inline void Update(int now)

    {

        tree[now].sum=tree[ls].sum+tree[rs].sum;

        tree[now].maxx=max(tree[ls].maxx,tree[rs].maxx);

        tree[now].minx=min(tree[ls].minx,tree[rs].minx);

    }

    inline void cover(int now,int D)

    {

        tree[now].cov=D; tree[now].tag=;

        tree[now].minx=tree[now].maxx=D;

        tree[now].sum=D*(tree[now].r-tree[now].l+);

    }

    inline void modify(int now,LL D)

    {

        tree[now].tag+=D;

        tree[now].minx+=D; tree[now].maxx+=D; tree[now].sum+=(tree[now].r-tree[now].l+)*D;

    }

    inline void PushDown(int now)

    {

        if (tree[now].l==tree[now].r) return;

        if (tree[now].cov!=-)

            cover(ls,tree[now].cov),cover(rs,tree[now].cov),tree[now].cov=-;

        if (tree[now].tag!=)

            modify(ls,tree[now].tag),modify(rs,tree[now].tag),tree[now].tag=;

    }

    inline void BuildTree(int now,int l,int r)

    {

        tree[now].l=l; tree[now].r=r; tree[now].cov=-;

        if (l==r) {tree[now].sum=tree[now].maxx=tree[now].minx=a[l]; return;}

        int mid=(l+r)>>;

        BuildTree(ls,l,mid); BuildTree(rs,mid+,r);

        Update(now);

    }

    inline void Modify(int now,int L,int R,int D)

    {

        int l=tree[now].l,r=tree[now].r;

        PushDown(now);

        if (L<=l && R>=r) {modify(now,D); return;}

        int mid=(l+r)>>;

        if (L<=mid) Modify(ls,L,R,D);

        if (R>mid) Modify(rs,L,R,D);

        Update(now);

    }

    inline void Change(int now,int L,int R)

    {

        int l=tree[now].l,r=tree[now].r;

        PushDown(now);

        if (L<=l && R>=r)

            {

                if ((int)sqrt(tree[now].maxx)==(int)sqrt(tree[now].minx))

                    {cover(now,(int)sqrt(tree[now].maxx)); return;}

                if (tree[now].maxx==tree[now].minx+)

                    {modify(now,(int)sqrt(tree[now].minx)-tree[now].minx); return;}

                if (l!=r) Change(ls,L,R),Change(rs,L,R);

                Update(now);

                return;

            }

        int mid=(l+r)>>;

        if (L<=mid) Change(ls,L,R);

        if (R>mid) Change(rs,L,R);

        Update(now);

    }

    inline LL Query(int now,int L,int R)

    {

        int l=tree[now].l,r=tree[now].r;

        PushDown(now);

        if (L<=l && R>=r) return tree[now].sum;

        int mid=(l+r)>>; LL re=;

        if (L<=mid) re+=Query(ls,L,R);

        if (R>mid) re+=Query(rs,L,R);

        return re;

    }

}

int main()

{

    N=read(),M=read();

    for (int i=; i<=N; i++) a[i]=read();

    SegmentTree::BuildTree(,,N);

    while (M--)

        {

            int opt=read(),l=read(),r=read(),D;

            switch (opt)

                {

                    case : D=read(),SegmentTree::Modify(,l,r,D); break;

                    case : SegmentTree::Change(,l,r); break;

                    case : printf("%lld\n",SegmentTree::Query(,l,r)); break;

                }

//            for (int i=1; i<=N; i++) printf("%d  ",SegmentTree::Query(1,i,i)); puts("=================");

        }

    return ;

}