题解 SP2713 【GSS4 - Can you answer these queries IV】

顾z

2018-08-15 21:05:15

Solution

**题目大意** 给定一个区间 支持**开方**和**查询区间值**操作 **(多组数据** **分析** 如果一个区间的最大值小于1,那就没有开方的必要了~~(具体不会证明,听大佬讲的~~ 一个数经过多次开方就会变成1~~(可以用计算器试一下~~ 因此我们维护一下区间最大值,维护一下区间和,对于一个区间的话,最大值开方后依旧为最大值,所以**对最大值以及区间和开方**即可。 由于是多组数据 所以需要每次**初始化** 可能分析与代码略有不同,思路是相同的 代码看不懂的来私信我吧~ [欢迎来玩](https://www.luogu.org/blog/RPdreamer/#) ------------------代码------------------- ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int #define ll long long using namespace std; ll n,m,t[400010],tg[400010]; ll cnt; IL void up(ll o) { t[o]=t[2*o]+t[2*o+1]; tg[o]=max(tg[2*o],tg[2*o+1]); return; }//维护区间最值的线段树 向上传递 IL void build(ll o,ll l, ll r) { if(l==r) { scanf("%lld",&t[o]); tg[o]=t[o]; return; } ll mid=l+r>>1; build(2*o,l,mid); build(2*o+1,mid+1,r); up(o); return; } IL void change(ll o,ll l,ll r,ll x,ll y) { if(tg[o]<=1)return;//最大值小于等于1的不做处理 if(l==r&&x<=l&&y>=r) { t[o]=sqrt(t[o]*1.0); tg[o]=t[o]; return ; } ll mid=l+r>>1; if(x<=mid)change(2*o,l,mid,x,y); if(y>mid)change(2*o+1,mid+1,r,x,y); up(o); return; } IL ll query(ll o,ll l,ll r,ll x,ll y) { if(x<=l&&y>=r)return t[o]; ll mid=l+r>>1; ll re=0; if(x<=mid)re+=query(2*o,l,mid,x,y); if(y>mid)re+=query(2*o+1,mid+1,r,x,y); return re; } //操作和普通线段树差不多哦 int main() { while(scanf("%lld",&n)!=EOF) { printf("Case #%d:\n",++cnt); memset(t,0,sizeof t); memset(tg,0,sizeof tg); build(1,1,n); scanf("%lld",&m); while(m--) { int k; ll l,r; scanf("%d%lld%lld",&k,&l,&r); if(l>r)swap(l,r); if(k==0)change(1,1,n,l,r); else printf("%lld\n",query(1,1,n,l,r)); } } } ```