UOJ #496.秋蝉鸣泣之时

不念不忘少年蓝@ 2021-09-30 05:26 252阅读 0赞

奇怪的题目背景 所误入的 是回忆的教室 所响起的 是通向绝望的计时器 所到达的 是开始的结束 你能相信吗? 题目背景 最近礼奈酱学会了线段树和树状数组两种数据结构 由于礼奈酱上课听的很认真，所以她知道 树状数组常见的操作是 单点加区间求和 线段树常见的操作是 区间加区间求和 但她认为自己已经不是小学生了,觉得只能维护加法标记这件事简直太蠢了~ 所以她将题目加强了一下，但她发现自己不会写这题的标程了 因为 rina酱非常可爱，所以你要帮她写这题的标程 题意描述 礼奈给了你一列数(n个) 要求支持以下两类操作共m次 区间求和 [L,R] 区间开平方[L,R]即将区间内每一个数Ai修改为 Ai−−√Ai 向下取整 输入输出格式 第一行 n 第二行 m 第三行n个数 表示 Ai 接下来m行 每行三个数 op,L,R op=1 为1操作 op=2 为2操作 对于每次1操作，请输出一行答案 样例输入 4 1 100 5 5 5 1 1 2 2 1 2 1 1 2 2 2 3 1 1 4 样例输出 101 11 11 数据范围 所有数据点保证 n,m≤2∗10^6,Ai≤10^9 本题中可以使用树状数组或线段树,大体思想是当一个数开方到1时,后面无论怎样开方都还是1,相同的,0开方后也还是0。那么只要去处理有大于1的数的区间即可。 由于题目中的每一个元素,最多只会开方5次,所以这道题就不会超时了。(另:树状数组需要并查集来辅助,将每个数的父亲设为它右边第一个不小于1的数,每次更新时将它的父亲并到它右边的数的父亲上,这样并查集数组会有递推性,即可以通过这种手段不断递推找到右边第一个不小于1的数)。 Code: //线段树 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=100005; int n,m,a[N]; long long sum[N*4],mx[N*4]; void build(int k,int l,int r){ if(l==r){ sum[k]=a[l]; mx[k]=sum[k]; return ; } int mid=(l+r)>>1; build(k*2,l,mid); build(k*2+1,mid+1,r); sum[k]=sum[k*2]+sum[k*2+1]; mx[k]=max(mx[k*2],mx[k*2+1]); } long long query(int k,int l,int r,int x,int y){ if(l>=x&&r<=y){ return sum[k]; } int mid=(l+r)>>1; long long res=0; if(x<=mid){ res+=query(k*2,l,mid,x,y); } if(mid<y){ res+=query(k*2+1,mid+1,r,x,y); } return res; } void update(int k,int l,int r,int x,int y){ if(mx[k]<=1){ return; } if(l==r){ sum[k]=sqrt(sum[k]); mx[k]=sum[k]; return; } int mid=(l+r)>>1; if(mid>=x){ update(k*2,l,mid,x,y); } if(mid<y){ update(k*2+1,mid+1,r,x,y); } sum[k]=sum[k*2]+sum[k*2+1]; mx[k]=max(mx[k*2],mx[k*2+1]); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } build(1,1,n); scanf("%d",&m); while(m--){ int opt,l,r; scanf("%d%d%d",&opt,&l,&r); if(l>r){ swap(l,r); } if(opt==1){ printf("%lld\n",query(1,1,n,l,r)); } else if(opt==2){ update(1,1,n,l,r); } } return 0; } //树状数组 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=100005; int n,m,a[N],fa[N],opt,l,r; long long c[N]; int find(int x){ if(x==fa[x]){ return x; } return fa[x]=find(fa[x]); } int lowbit(int x){ return x&-x; } void update(int i,int val){ while(i<=n){ c[i]+=val; i+=lowbit(i); } } long long sum(int i){ long long ans=0; while(i){ ans+=c[i]; i-=lowbit(i); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); update(i,a[i]); } scanf("%d",&m); for(int i=1;i<=n;i++){ if(a[i]<=1){ fa[i]=i+1; } else{ fa[i]=i; } } fa[n+1]=n+1; while(m--){ scanf("%d%d%d",&opt,&l,&r); if(opt==1){ printf("%lld\n",sum(r)-sum(l-1)); } else if(opt==2){ for(int i=l;i<=r;i=find(i+1)){ int res=(int)sqrt(a[i]); update(i,res-a[i]); a[i]=res; if(a[i]<=1){ fa[i]=find(i+1); } } } } return 0; }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11198492.html