BZOJ3211: 花神游历各国（线段树）

3211: 花神游历各国

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 5692  Solved: 2114
[Submit][Status][Discuss]

Description

 

Input

 

Output

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

Sample Input

4

1 100 5 5

5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Sample Output

101

11

11

HINT

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

Source

SPOJ2713 gss4 数据已加强

裸题。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

using namespace std;

const int maxn=;

int Mx[maxn]; ll sum[maxn];

void pushup(int Now){

    sum[Now]=sum[Now<<]+sum[Now<<|];

    Mx[Now]=max(Mx[Now<<],Mx[Now<<|]);

}

void build(int Now,int L,int R)

{

    if(L==R) {

        scanf("%d",&Mx[Now]);sum[Now]=Mx[Now];

        return ;

    }

    int Mid=(L+R)>>;

    build(Now<<,L,Mid); build(Now<<|,Mid+,R);

    pushup(Now);

}

ll query(int Now,int L,int R,int l,int r)

{

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

    int Mid=(L+R)>>; ll res=;

    if(l<=Mid) res+=query(Now<<,L,Mid,l,r);

    if(r>Mid) res+=query(Now<<|,Mid+,R,l,r);

    return res;

}

void Sqrt(int Now,int L,int R)

{

    if(L==R){ sum[Now]=Mx[Now]=sqrt(Mx[Now]); return ;}

    if(Mx[Now]<=) return ;

    int Mid=(L+R)>>;

    Sqrt(Now<<,L,Mid); Sqrt(Now<<|,Mid+,R);

    pushup(Now);

}

void update(int Now,int L,int R,int l,int r)

{

    if(Mx[Now]<=) return ;

    if(l<=L&&r>=R){ Sqrt(Now,L,R);return ;}

    int Mid=(L+R)>>;

    if(l<=Mid) update(Now<<,L,Mid,l,r);

    if(r>Mid) update(Now<<|,Mid+,R,l,r);

    pushup(Now);

}

int main()

{

    int N,M,L,R,opt;

    scanf("%d",&N);

    build(,,N);

    scanf("%d",&M);

    rep(i,,M){

        scanf("%d%d%d",&opt,&L,&R);

        if(opt==) printf("%lld\n",query(,,N,L,R));

        else update(,,N,L,R);

    }

    return ;

}