奇怪的题目背景
所误入的 是回忆的教室
所响起的 是通向绝望的计时器
所到达的 是开始的结束
你 能相信吗?
题目背景
最近礼奈酱学会了线段树和树状数组两种数据结构
由于礼奈酱上课听的很认真，所以她知道
树状数组常见的操作是 单点加区间求和
线段树常见的操作是 区间加区间求和
但她认为自己已经不是小学生了,觉得只能维护加法标记这件事简直太蠢了~
所以她将题目加强了一下，但她发现自己不会写这题的标程了
因为 rina
rina
酱非常可爱，所以你要帮她写这题的标程
题意描述
礼奈给了你一列数(n
n
个)
要求支持以下两类操作共m
m
次
1.区间求和 [L,R]
[L,R]
即∑ R i=L A i
∑i=LRAi
2.区间开平方[L,R]
[L,R]
即将区间内每一个数A i
Ai
修改为 A i − − √
Ai
向下取整
输入输出格式
第一行 n
n
第二行 m
m
第三行n
n
个数 表示 A i
Ai
接下来m
m
行
每行三个数 op,L,R
op,L,R
op=1
op=1
为1操作
op=2
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 ,A i ≤10 9
n,m≤2∗106,Ai≤109
#include <bits/stdc++.h> using namespace std; #define int long long int n,m; int l[10005],r[10005]; int a[100005]; int f[10005]; int w[100005]; signed main() { scanf("%lld",&n); int len=sqrt(n); r[0]=0; int cnt=0; while(r[cnt]<=n) { cnt++; l[cnt]=r[cnt-1]+1; r[cnt]=l[cnt]+len; } r[cnt]=n; for(int i=1;i<=cnt;++i) { int flag=0; for(int j=l[i];j<=r[i];++j) { w[j]=i; if(a[j]!=1) { flag=1; } } if(flag==0) { f[i]=1; } } for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); } scanf("%lld",&m); int x,y,z; for(int i=1;i<=m;++i) { scanf("%lld%lld%lld",&x,&y,&z); if(x==0) { if(w[y]==w[z]) { for(int j=y;j<=z;++j) { a[j]=floor(sqrt(a[j])*1.0); } continue; } for(int j=y;j<=r[w[y]];++j) { a[j]=floor(sqrt(a[j]*1.0)); } for(int j=l[w[z]];j<=z;++j) { a[j]=floor(sqrt(a[j]*1.0)); } for(int j=w[y]+1;j<=w[z]-1;++j) { if(f[j]==1) { continue; } else { for(int k=l[j];k<=r[j];++k) { a[k]=floor(sqrt(a[k]*1.0)); } int sum=0; for(int k=l[j];k<=r[j];++k) { if(a[k]==1) { sum++; } } if(sum==r[j]-l[j]+1) { f[j]=1; } } } } else { int ans=0; if(w[y]==w[z]) { for(int j=y;j<=z;++j) { ans+=a[j]; } printf("%lld\n",ans); continue; } if(f[w[y]]==1) { ans+=r[w[y]]-y+1; } else { for(int j=y;j<=r[w[y]];++j) { ans+=a[j]; } } if(f[w[z]]==1) { ans+=z-l[w[z]]+1; } else { for(int j=l[w[z]];j<=z;++j) { ans+=a[j]; } } for(int j=w[y]+1;j<=w[z]-1;++j) { if(f[j]==1) { ans+=r[j]-l[j]+1; } else { for(int k=l[j];k<=r[j];++k) { ans+=a[k]; } } } printf("%lld\n",ans); } } return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146
