BZOJ 3211(花神游历各国-线段树区间开方)

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 52 Solved: 24
[Submit][Status][Discuss]
Description

Input

Output
每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input
4

1 100 5 5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Sample Output

101

HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

Source
SPOJ2713 数据已加强

不用犹豫，本题正宗线段树。

不过线段树不支持区间开方，但是10^9最多开5次方就到1了-_-

所以暴力改也就MAXN*5 无压力。

用线段树存储一段是否需要开方（2-需要,1-不用)+暴力改

无压力

[cpp] #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (200000+10)
#define MAXM (400000+10)
#define Lson (x<<1)
#define Rson ((x<<1)+1)
int n,m,a[MAXN*2]={0},b[MAXN*2]={0};
long long sum[MAXN*2];
void update(int x)
{
    if (b[Lson]==2||b[Rson]==2) b[x]=2;
    else b[x]=1;
    sum[x]=sum[Lson]+sum[Rson];
}
void build(int x,int l,int r)
{
    if (l==r)
    {
        scanf("%d",&a[x]);sum[x]=a[x];
        if (a[x]<=1) b[x]=1;
        else b[x]=2;
    }
    if (l>=r) return;
    int m=(l+r)>>1;
    build(Lson,l,m);
    build(Rson,m+1,r);
    update(x);
}
void pushdown(int x,int l,int r)
{
    if (b[x]<=1) return;
    if (l==r)
    {
        a[x]=sum[x]=sqrt(a[x]);
        if (a[x]<=1) b[x]=1;
        return;
    }
    int m=(l+r)>>1;
    pushdown(Lson,l,m);
    if (m<r) pushdown(Rson,m+1,r);
    update(x);
}
void change(int x,int l,int r,int L,int R)
{
    if (b[x]<=1) return;
    int m=(l+r)>>1;
    if (L<=l&&r<=R)
    {
        pushdown(x,l,r);
        return;
    }
    if (L<=m) change(Lson,l,m,L,R);
    if (m<R) change(Rson,m+1,r,L,R);
    update(x);
}
long long qur(int x,int l,int r,int L,int R)
{
    int m=(l+r)>>1;
    if (L<=l&&r<=R)
    {
        return sum[x];
    }
    long long ans=0;
    if (L<=m) ans+=qur(Lson,l,m,L,R);
    if (m<R) ans+=qur(Rson,m+1,r,L,R);
    return ans;
}

int main()
{
// freopen("bzoj3211.in","r",stdin);
// freopen(".out","w",stdout);
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&m);
    For(i,m)
    {
        int x,l,r;
        scanf("%d%d%d",&x,&l,&r);
        if (x==1) printf("%lld\n",qur(1,1,n,l,r));
        else change(1,1,n,l,r);
    }
    return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (200000+10)
#define MAXM (400000+10)
#define Lson (x<<1)
#define Rson ((x<<1)+1)
int n,m,a[MAXN*2]={0},b[MAXN*2]={0};
long long sum[MAXN*2];
void update(int x)
{
if (b[Lson]==2||b[Rson]==2) b[x]=2;
else b[x]=1;
sum[x]=sum[Lson]+sum[Rson];
}
void build(int x,int l,int r)
{
if (l==r)
{
  scanf("%d",&a[x]);sum[x]=a[x];
  if (a[x]<=1) b[x]=1;
  else b[x]=2;
}
if (l>=r) return;
int m=(l+r)>>1;
build(Lson,l,m);
build(Rson,m+1,r);
update(x);
}
void pushdown(int x,int l,int r)
{
if (b[x]<=1) return;
if (l==r)
{
  a[x]=sum[x]=sqrt(a[x]);
  if (a[x]<=1) b[x]=1;
  return;
}
int m=(l+r)>>1;
pushdown(Lson,l,m);
if (m<r) pushdown(Rson,m+1,r);
update(x);
}
void change(int x,int l,int r,int L,int R)
{
if (b[x]<=1) return;
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
  pushdown(x,l,r);
  return;
}
if (L<=m) change(Lson,l,m,L,R);
if (m<R) change(Rson,m+1,r,L,R);
update(x);
}
long long qur(int x,int l,int r,int L,int R)
{
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
  return sum[x];
}
long long ans=0;
&nbs

补充：软件开发 , C++ ,