【題目描述】

給出一個長為 n 的數列，以及 n 個操作，操作涉及區間開方，區間求和。

【輸入格式】

第一行輸入一個數字 n。

第二行輸入 n?個數字，第 i 個數字為 ai，以空格隔開。

接下來輸入 n 行詢問，每行輸入四個數字 opt、l、r、c，以空格隔開。

若 opt=0，表示將位于 [l,r] 的之間的數字都開方，對于區間中的每個 ai(l<=i<=r)，ai->|√ai|

若 opt=1，表示詢問位于 [l,r] 的所有數字的和。

【輸出格式】

對于每次詢問，輸出一行一個數字表示答案。

【樣例】

樣例輸入
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

樣例輸出
6
2

【數據范圍與提示】

對于 100%?的數據，1<=n<=50000,-2^31<=other,ans<=2^31-1。

【源代碼】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; LL block,sum;//block為塊的長度，sum為塊的個數 LL a[N]; LL pos[N];//pos記錄第i個元素在第幾個塊中 LL ans[N];//維護整塊和 bool flag[N];//標記整塊是否全為1 void init(LL n){block=sqrt(n);//塊的長度sum=n/block;//塊個數if(n%block)sum++;for(LL i=1;i<=n;i++)//第i個元素在第幾塊中pos[i]=(i-1)/block+1; } void work(LL L,LL R,LL x){//維護整塊和LL start=0;for(LL i=L;i<=R;i++)start+=a[i];ans[x]=start; } void update(LL L,LL R){for(LL i=L;i<=min(pos[L]*block,R);i++){//左邊的邊角料ans[pos[L]]-=a[i];//開方前元素和減去第i個元素a[i]=sqrt(a[i]);//開方ans[pos[L]]+=a[i];//開方后元素和加上第i個元素}if(pos[L]!=pos[R]){//存在右區間才遍歷，防止重復計算for(LL i=(pos[R]-1)*block+1;i<=R;i++){//右邊的邊角料ans[pos[R]]-=a[i];//開方前元素和減去第i個元素a[i]=sqrt(a[i]);//開方ans[pos[R]]+=a[i];//開方后元素和加上第i個元素}}for(LL i=pos[L]+1;i<=pos[R]-1;i++){//中間的整塊if(flag[i])//全為1，跳過continue;else{//不全為1，暴力處理flag[i]=true;//先假設為1，如果不是后面再改為0for(int j=(i-1)*block+1;j<=i*block;j++){//塊中的所有元素ans[i]-=a[j];//開方前元素和減去第j個元素a[j]=sqrt(a[j]);//開方ans[i]+=a[j];//開方后元素和加上第j個元素if(a[j]!=1)//不全為1flag[i]=false;}}} } LL query(LL L,LL R){LL res=0;for(LL i=L;i<=min(pos[L]*block,R);i++){//左邊的邊角料res+=a[i];}if(pos[L]!=pos[R]){//存在右區間才遍歷，防止重復計算for(LL i=(pos[R]-1)*block+1;i<=R;i++){//右邊的邊角料res+=a[i];}}for(LL i=pos[L]+1;i<=pos[R]-1;i++){//中間的整塊進行二分查找res+=ans[i];}return res; } int main(){LL n;scanf("%lld",&n);for(LL i=1;i<=n;i++)scanf("%lld",&a[i]);init(n);for(LL i=1;i<=sum;i++)//傳入塊的左右邊界與編號work((i-1)*block+1,i*block,i);for(LL i=1;i<=n;i++){LL op;LL left,right,x;scanf("%lld",&op);scanf("%lld%lld%lld",&left,&right,&x);if(op==0)update(left,right);else if(op==1)printf("%lld\n",query(left,right));}return 0; }

?

總結

以上是生活随笔為你收集整理的数列分块入门 5（LibreOj-6281）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。