ybt.1550 花神游历各国题解

本文主要是介绍ybt.1550 花神游历各国题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

花神喜欢步行游历各国，顺便虐爆各地竞赛。花神有一条游览路线，它是线型的，也就是说，所有游历国家呈一条线的形状排列，花神对每个国家都有一个喜欢程度（当然花神并不一定喜欢所有国家）。

每一次旅行中，花神会选择一条旅游路线，它在那一串国家中是连续的一段，这次旅行带来的开心值是这些国家的喜欢度的总和，当然花神对这些国家的喜欢程序并不是恒定的，有时会突然对某些国家产生反感，使他对这些国家的喜欢度 $\delta i$ 变为 $\sqrt{\delta i}$ （可能是花神虐爆了那些国家的 OI，从而感到乏味）。

现在给出花神每次的旅行路线，以及开心度的变化，请求出花神每次旅行的开心值。

【Input】

第一行是一个整数 NN，表示有 NN 个国家；

第二行有 NN 个空格隔开的整数，表示每个国家的初始喜欢度 $\delta i$ ；

第三行是一个整数 MM，表示有 MM 条信息要处理；

第四行到最后，每行三个整数 x,l,rx,l,r，当 x = 1时询问游历国家 ll 到 rr 的开心值总和，就是 $$$\sum_{i=l}^r{\delta i}$ ，当 x = 2 时国家 ll 到 rr 中每个国家的喜欢度 $\delta i$ 变为 $\sqrt{\delta i}$ 。

【Output】

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

【Sample Input】

【Sample Output】

101
11
11

【Data range & Tips】

对于全部数据， $1\leq n\leq 10^5,1\leq m\leq 2\times 10^5,1\leq l \leq r \leq n,0\leq \delta i\leq 10^9$

注：建议使用 sqrt 函数，且向下取整。

【Solution】

$n^2\log n$ 没跑满，然后过了（神奇）！

区间修改时不打懒标记，把区间内每个叶子节点都遍历（我不知道开根号怎么打懒标记）

然后有个小优化：

维护maxn记录当前区间最大的数，因为1,0开方和原值一样，所以当 $maxn\leq 1$ 时就return;

【Code】

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct Segment_Tree{long long sum,maxn;
}tree[1000000];
int n,m,a[100100],op,ll,rr;
inline void build(int k,int l,int r){if(l==r){tree[k].sum=a[l];tree[k].maxn=a[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn);
}
inline void modify(int k,int l,int r,int x,int y){if(l>y||r<x)return;if(tree[k].maxn<=1)return;if(l==r){tree[k].sum=floor(sqrt(tree[k].sum));tree[k].maxn=tree[k].sum;return;}int mid=(l+r)>>1;if(x<=mid)modify(k<<1,l,mid,x,y);if(y>mid)modify(k<<1|1,mid+1,r,x,y);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn); 
}
inline long long Ask(int k,int l,int r,int x,int y){if(l>y||r<x)return 0;if(l>=x&&r<=y)return tree[k].sum;int mid=(l+r)>>1;long long res=0;if(x<=mid)res+=Ask(k<<1,l,mid,x,y);if(y>mid)res+=Ask(k<<1|1,mid+1,r,x,y);return res;
}
int main(){scanf("%d",&n);for(register int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);scanf("%d",&m);for(register int i=1;i<=m;i++){scanf("%d%d%d",&op,&ll,&rr);if(op==1){printf("%lld\n",Ask(1,1,n,ll,rr)); }else{modify(1,1,n,ll,rr);}}return 0;
}

这篇关于ybt.1550 花神游历各国题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！