BZOJ 3211【线段树】

题意：

n个数，m个操作。

1,L,R 询问[L , R] 的总和。

2,L,R 将区间所有数都开根号。

思路：

区间和简单。

主要就是一个区间所有元素相同的标记Same ，但是这样是不是要求太高？

sqrt 好像就算是1e9，也down的非常快到1了，且这里还没有区间加。

so，只要考虑标记区间是否都是1/0就足够了。

水题。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

struct Seg{

    int Left,Right;

    int Flag;

    LL Sum;

}q[N*4];

void Build(int num,int Left,int Right){

    q[num].Left=Left;q[num].Right=Right;

    if(Left == Right){

        scanf("%lld",&q[num].Sum);

        if(q[num].Sum==0 || q[num].Sum==1)

            q[num].Flag=1;

        return;

    }

    int Mid=(Left+Right)>>1;

    Build(num<<1,Left,Mid);

    Build(num<<1|1,Mid+1,Right);

    q[num].Sum=q[num<<1].Sum+q[num<<1|1].Sum;

    q[num].Flag=q[num<<1].Flag&q[2*num|1].Flag;

}

void Update(int num,int Left,int Right)

{

    if(q[num].Flag) return;

    if(q[num].Left==q[num].Right)

    {

        q[num].Sum=sqrt(q[num].Sum);

        if(q[num].Sum==0||q[num].Sum==1) q[num].Flag=1;

        return;

    }

    int Mid=(q[num].Left+q[num].Right)>>1;

    if(Mid>=Right) Update(num<<1,Left,Right);

    else if(Mid<Left) Update(num<<1|1,Left,Right);

    else

    {

        Update(num<<1,Left,Mid);

        Update(num<<1|1,Mid+1,Right);

    }

    q[num].Sum=q[num<<1].Sum+q[num<<1|1].Sum;

    q[num].Flag=q[num<<1].Flag&q[num<<1|1].Flag;

}

LL Query(int num,int Left,int Right)

{

    if(q[num].Left>=Left && q[num].Right<=Right)

        return q[num].Sum;

    int Mid=(q[num].Left+q[num].Right)>>1;

    if(Mid>=Right) return Query(num<<1,Left,Right);

    else if(Mid<Left) return Query(num<<1|1,Left,Right);

    else

        return Query(num<<1,Left,Mid)+Query(num<<1|1,Mid+1,Right);

}

int main()

{

    int n,Q;

    int op,Left,Right;

    scanf("%d",&n);

    Build(1,1,n);

    scanf("%d",&Q);

    while(Q--)

    {

        scanf("%d%d%d",&op,&Left,&Right);

        switch(op){

            case 1:printf("%lld\n",Query(1,Left,Right));break;

            case 2:Update(1,Left,Right);break;

        }

    }

    return 0;

}

巴特西

BZOJ 3211【线段树】

最新文章

热门文章