链接
\(huangjunsen\) ， \(Luogu\) \(P4145\)
给定一个区间，要求区间开方（向下取整），区间求和。
线段树区间暴力修改、区间查询模板。维护每个区间和 \(sum\) 、区间最大值 \(maxn\) 。 这题的特点在于区间开方（向下取整）这个操作不具有区间可加性，因此不能打标记维护。又因为 \(\sqrt{1}=1\) ， \(\sqrt{0}=0\) ，所以区间最大值小于等于\(1\)时该区间均不需要更新。而区间内每个和均在 \(10^{18}\) 以内，而 \(10^{18}\) 连续 \(6\) 次区间开方（向下取整）后即为 \(1\) ，所以每个数修改不超过 \(6\) 次，所有修改操作的总时间复杂度为 \(O(n)\) 。而查询的时间复杂度为 \(O(log\) \(n)\) ，故总时间复杂度符合题意。
\(1.\) 区间操作 \([l,r]\) 先确保 \(l>r\) 。
\(1.\) 建树记得赋左右端点。。。。。。
\(2.\) 注意鬼畜的输出格式。。。。。。
\(3.\) 注意滑稽的数据范围。。。。。。
\(4.\) 注意询问的是什么值。。。。。。
\(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 tmp,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)/2; if(l<=mid) val+=query(pos<<1,l,r); if(mid<r) val+=query(pos<<1|1,l,r); return val; } int main() { n=read(); 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) { tmp=l; l=r; r=tmp; } if(!op) modify(1,l,r); else printf("%lld\n",query(1,l,r)); } return 0; }转载于:https://www.cnblogs.com/Peter0701/p/11378976.html
相关资源：JAVA上百实例源码以及开源项目