转载

$SP2713$ $GSS4$ $-$ $Can$ $you$ $answer$ $these$ $queries$ $IV$

链接

背景

\(Fudan\) \(University\) \(Problem\) \(Setters\)\(2008.5.21\)\(SP\) \(1716\)

题意

给定一个区间,要求区间开方(向下取整),区间求和。

解法

线段树区间暴力修改、区间查询模板。维护每个区间和 \(sum\) 、区间最大值 \(maxn\)
这题的特点在于区间开方(向下取整)这个操作不具有区间可加性,因此不能打标记维护。又因为 \(\sqrt{1}=1\)\(\sqrt{0}=0\) ,所以区间最大值小于等于\(1\)时该区间均不需要更新。而区间内每个和均在 \(10^{18}\) 以内,而 \(10^{18}\) 连续 \(6\) 次区间开方(向下取整)后即为 \(1\) ,所以每个数修改不超过 \(6\) 次,所有修改操作的总时间复杂度为 \(O(n)\) 。而查询的时间复杂度为 \(O(log\) \(n)\) ,故总时间复杂度符合题意。

\(trick\)

\(1.\) 区间操作 \([l,r]\) 先确保 \(l>r\)

细节

\(1.\) 建树记得赋左右端点。。。。。。

\(2.\) 注意鬼畜的输出格式。。。。。。

\(3.\) 注意滑稽的数据范围。。。。。。

\(4.\) 多组数据要记得清空。。。。。。

\(5.\) 注意询问的是什么值。。。。。。

代码

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } inline long long readl() { long long ret=0; int f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int cas,n,q,op,l,r; long long a[100005]; struct SegmentTree { int l,r; long long sum,maxn; }t[400005]; void build(int pos,int l,int r) { t[pos].l=l; t[pos].r=r; if(l==r) { t[pos].sum=a[l]; t[pos].maxn=a[l]; return; } int mid=(l+r)/2; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum; t[pos].maxn=max(t[pos<<1].maxn,t[pos<<1|1].maxn); } void modify(int pos,int l,int r) { if(t[pos].l==t[pos].r) { t[pos].sum=(long long)sqrt(t[pos].sum); t[pos].maxn=(long long)sqrt(t[pos].maxn); return; } int mid=(t[pos].l+t[pos].r)/2; if(l<=mid&&1<t[pos<<1].maxn) modify(pos<<1,l,r); if(mid<r&&1<t[pos<<1|1].maxn) modify(pos<<1|1,l,r); t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum; t[pos].maxn=max(t[pos<<1].maxn,t[pos<<1|1].maxn); } long long query(int pos,int l,int r) { if(l<=t[pos].l&&t[pos].r<=r) return t[pos].sum; long long val=0; int mid=(t[pos].l+t[pos].r)>>1; if(l<=mid) val+=query(pos<<1,l,r); if(mid<r) val+=query(pos<<1|1,l,r); return val; } int main() { while(scanf("%d",&n)!=EOF) { cas++; printf("Case #%d:\n",cas); memset(t,0,sizeof(t)); for(register int i=1;i<=n;i++) a[i]=readl(); build(1,1,n); q=read(); while(q--) { op=read(); l=read(); r=read(); if(r<l) swap(l,r); if(!op) modify(1,l,r); else printf("%lld\n",query(1,l,r)); } printf("\n"); } return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11372557.html

正文到此结束
本文目录