秋蟬鳴泣之時

奇怪的題目背景

所誤入的 是回憶的教室

所響起的 是通向絕望的計時器

所到達的 是開始的結束

你 能相信嗎?

題目背景

最近禮奈醬學會了線段樹和樹狀數組兩種數據結構

由于禮奈醬上課聽的很認真，所以她知道

樹狀數組常見的操作是 單點加區間求和

線段樹常見的操作是 區間加區間求和

但她認為自己已經不是小學生了,覺得只能維護加法標記這件事簡直太蠢了~

所以她將題目加強了一下，但她發現自己不會寫這題的標程了

因為?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;
}