BZOJ 3211: 花神游历各国

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解
代码

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

题解

这里的修改只有sqrt是吧。那么一个数一直sqrt就变成1了，那么之后就不用对它进行修改操作了！所以我们记录一个区间最大值，如果最大值大于1我们才修改这个区间。
P.S. 一开始看错题了，以为这题要动态修改+Sqrt 求区间最大连续子区间最大和QuQ 最近脑子不太好= =

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int Maxn=100010;
struct Btree{
    int left,right;
    long long sum,max;
};
Btree tree[Maxn*4+5];
long long data[Maxn];
int n,m;
inline long long remax(long long a,long long b){return (a>b?a:b);}
inline void merge(int x){
    if (tree[x].left==tree[x].right) return ;
    int lx=x*2,rx=x*2+1;
    tree[x].sum=tree[lx].sum+tree[rx].sum;
    tree[x].max=remax(tree[lx].max,tree[rx].max);
}
void build(int x,int left,int right){
    tree[x].left=left;
    tree[x].right=right;
    if (left==right){
        tree[x].max=tree[x].sum=data[left];
    }else{
        int mid=(left+right)/2;
        build(x*2,left,mid);
        build(x*2+1,mid+1,right);
        merge(x);
    }
}
void change(int x,int left,int right){
    if (tree[x].left==tree[x].right){
        tree[x].sum=sqrt(tree[x].sum);
        tree[x].max=tree[x].sum;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid && tree[x*2].max>1) change(x*2,left,right);
        if (right>mid && tree[x*2+1].max>1) change(x*2+1,left,right);
        merge(x);
    }
}
long long query(int x,int left,int right){
    if (left<=tree[x].left && tree[x].right<=right){
        return tree[x].sum;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        long long Ans=0;
        if (left<=mid) Ans+=query(x*2,left,right);
        if (right>mid) Ans+=query(x*2+1,left,right);
        return Ans;
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&data[i]);
    build(1,1,n);
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        int x,l,r;
        scanf("%d%d%d",&x,&l,&r);
        switch(x){
            case 1:
                printf("%lldn",query(1,l,r));
                break;
            case 2:
                change(1,l,r);
                break;
        }
    }
    return 0;
}

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int Maxn=100010;

struct Btree{

int left,right;

long long sum,max;

};

Btree tree[Maxn*4+5];

long long data[Maxn];

int n,m;

inline long long remax(long long a,long long b){return (a>b?a:b);}

inline void merge(int x){

if (tree[x].left==tree[x].right) return ;

int lx=x*2,rx=x*2+1;

tree[x].sum=tree[lx].sum+tree[rx].sum;

tree[x].max=remax(tree[lx].max,tree[rx].max);

}

void build(int x,int left,int right){

tree[x].left=left;

tree[x].right=right;

if (left==right){

tree[x].max=tree[x].sum=data[left];

}else{

int mid=(left+right)/2;

build(x*2,left,mid);

build(x*2+1,mid+1,right);

merge(x);

}

void change(int x,int left,int right){

if (tree[x].left==tree[x].right){

tree[x].sum=sqrt(tree[x].sum);

tree[x].max=tree[x].sum;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid && tree[x*2].max>1) change(x*2,left,right);

if (right>mid && tree[x*2+1].max>1) change(x*2+1,left,right);

merge(x);

}

long long query(int x,int left,int right){

if (left<=tree[x].left && tree[x].right<=right){

return tree[x].sum;

}else{

int mid=(tree[x].left+tree[x].right)/2;

long long Ans=0;

if (left<=mid) Ans+=query(x*2,left,right);

if (right>mid) Ans+=query(x*2+1,left,right);

return Ans;

}

int main(){

scanf("%d",&n);

for (int i=1;i<=n;i++) scanf("%lld",&data[i]);

build(1,1,n);

scanf("%d",&m);

for (int i=1;i<=m;i++){

int x,l,r;

scanf("%d%d%d",&x,&l,&r);

switch(x){

case 1:

printf("%lldn",query(1,l,r));

break;

case 2:

change(1,l,r);

break;

}

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑