LOJ #6281. 数列分块入门 5-分块(区间开方、区间求和)

内存限制：256 MiB时间限制：500 ms标准输入输出

题目类型：传统评测方式：文本比较

上传者： hzwer

提交提交记录统计测试数据讨论

给出一个长为 $a_1ldots a_na1…an，以及 nn 个操作，操作涉及区间开方，区间求和。$

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若 $a_i(lle ile r),: a_i ← leftlfloor sqrt{a_i} ight floorai(l≤i≤r),ai←⌊ai⌋$

若

对于每次询问，输出一行一个数字表示答案。

样例输入

样例输出

6
2

对于 $100\%100% 的数据，1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

  1 //#6281. 数列分块入门 5-区间开方，区间求和
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn=5e4+10;
  6 
  7 int n,m,pos[maxn],tag[maxn];
  8 ll a[maxn],b[maxn];
  9 
 10 void rechange(int x)
 11 {
 12     int flag=0;
 13     for(int i=(x-1)*m+1;i<=min(x*m,n);i++){
 14         if(a[i]>1) flag=1;
 15     }
 16     if(!flag) tag[x]=0;
 17 }
 18 
 19 void update(int l,int r)
 20 {
 21     if(pos[l]==pos[r]){
 22         if(tag[pos[l]]){
 23             for(int i=l;i<=r;i++){
 24                 b[pos[l]]-=a[i];
 25                 a[i]=floor(sqrt(a[i]));
 26                 b[pos[l]]+=a[i];
 27             }
 28             rechange(pos[l]);
 29         }
 30     }
 31     else{
 32         if(tag[pos[l]]){
 33             for(int i=l;i<=pos[l]*m;i++){
 34                 b[pos[l]]-=a[i];
 35                 a[i]=floor(sqrt(a[i]));
 36                 b[pos[l]]+=a[i];
 37             }
 38             rechange(pos[l]);
 39         }
 40         for(int i=pos[l]+1;i<pos[r];i++){
 41             if(!tag[i]) continue;
 42             for(int j=(i-1)*m+1;j<=i*m;j++){
 43                 b[i]-=a[j];
 44                 a[j]=floor(sqrt(a[j]));
 45                 b[i]+=a[j];
 46             }
 47             rechange(i);
 48         }
 49         if(tag[pos[r]]){
 50             for(int i=(pos[r]-1)*m+1;i<=r;i++){
 51                 b[pos[r]]-=a[i];
 52                 a[i]=floor(sqrt(a[i]));
 53                 b[pos[r]]+=a[i];
 54             }
 55             rechange(pos[r]);
 56         }
 57     }
 58 }
 59 
 60 ll query(int l,int r)
 61 {
 62     ll ans=0;
 63     if(pos[l]==pos[r]){
 64         for(int i=l;i<=r;i++){
 65             ans+=a[i];
 66         }
 67     }
 68     else{
 69         for(int i=l;i<=pos[l]*m;i++){
 70             ans+=a[i];
 71         }
 72         for(int i=pos[l]+1;i<pos[r];i++){
 73             ans+=b[i];
 74         }
 75         for(int i=(pos[r]-1)*m+1;i<=r;i++){
 76             ans+=a[i];
 77         }
 78     }
 79     return ans;
 80 }
 81 
 82 int main()
 83 {
 84     scanf("%d",&n);
 85     m=sqrt(n);
 86     for(int i=1;i<=n;i++){
 87         scanf("%lld",&a[i]);
 88         pos[i]=(i-1)/m+1;
 89     }
 90     for(int i=1;i<=n;i++){
 91         int cnt=log(a[i])/log(2);
 92         if(cnt>=1) tag[pos[i]]=1;
 93     }
 94     for(int i=1;i<=m+1;i++){
 95         ll cnt=0;
 96         for(int j=(i-1)*m+1;j<=min(i*m,n);j++){
 97             cnt+=a[j];
 98         }
 99         b[i]=cnt;
100     }
101     for(int i=1;i<=n;i++){
102         int op,l,r,c;
103         scanf("%d%d%d%d",&op,&l,&r,&c);
104         if(op==0){
105             update(l,r);
106         }
107         else{
108             printf("%lld
",query(l,r));
109         }
110     }
111 }
112 
113 
114 /*
115 10
116 1 3 4 2 5 7 11 3 5 1
117 0 1 5 1
118 1 1 7 2
119 0 3 9 1
120 1 4 8 7
121 1 1 10 6
122 1 3 5 3
123 1 5 10 7
124 1 6 10 6
125 1 2 7 4
126 1 3 7 5
127 
128 25
129 8
130 14
131 3
132 10
133 9
134 9
135 8
136 */

代码二：

  1 //#6281. 数列分块入门 5-区间开方，区间求和(忘注释掉了，导致超时+wa，蠢死了)
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn=5e4+10;
  6 
  7 int n,m,pos[maxn],tag[maxn];
  8 ll a[maxn],b[maxn];
  9 
 10 void rechange(int x)
 11 {
 12     ll cnt=0;int flag=0;
 13     for(int i=(x-1)*m+1;i<=min(x*m,n);i++){
 14         cnt+=a[i];
 15         if(a[i]>=2) flag=1;
 16     }
 17     b[x]=cnt;
 18     if(!flag) tag[x]=0;
 19 }
 20 
 21 void update(int l,int r)
 22 {
 23     if(pos[l]==pos[r]){
 24         if(tag[pos[l]]){
 25             for(int i=l;i<=r;i++){
 26                 a[i]=floor(sqrt(a[i]));
 27             }
 28             rechange(pos[l]);
 29         }
 30     }
 31     else{
 32         if(tag[pos[l]]){
 33             for(int i=l;i<=pos[l]*m;i++){
 34                 a[i]=floor(sqrt(a[i]));
 35             }
 36             rechange(pos[l]);
 37         }
 38         for(int i=pos[l]+1;i<pos[r];i++){
 39             if(!tag[i]) continue;
 40             for(int j=(i-1)*m+1;j<=i*m;j++){
 41                 a[j]=floor(sqrt(a[j]));
 42             }
 43             rechange(i);
 44         }
 45         if(tag[pos[r]]){
 46             for(int i=(pos[r]-1)*m+1;i<=r;i++){
 47                 a[i]=floor(sqrt(a[i]));
 48             }
 49             rechange(pos[r]);
 50         }
 51     }
 52 }
 53 
 54 ll query(int l,int r)
 55 {
 56     ll ans=0;
 57     if(pos[l]==pos[r]){
 58         for(int i=l;i<=r;i++){
 59             ans+=a[i];
 60         }
 61     }
 62     else{
 63         for(int i=l;i<=pos[l]*m;i++){
 64             ans+=a[i];
 65         }
 66         for(int i=pos[l]+1;i<pos[r];i++){
 67             ans+=b[i];
 68         }
 69         for(int i=(pos[r]-1)*m+1;i<=r;i++){
 70             ans+=a[i];
 71         }
 72     }
 73     //cout<<"ans: "<<ans<<endl;
 74     return ans;
 75 }
 76 
 77 int main()
 78 {
 79     scanf("%d",&n);
 80     m=sqrt(n);
 81     for(int i=1;i<=n;i++){
 82         scanf("%lld",&a[i]);
 83         pos[i]=(i-1)/m+1;
 84     }
 85     for(int i=1;i<=n;i++){
 86         int cnt=log(a[i])/log(2);
 87         if(cnt>=1) tag[pos[i]]=1;
 88     }
 89     for(int i=1;i<=m+1;i++){
 90         ll cnt=0;
 91         for(int j=(i-1)*m+1;j<=min(i*m,n);j++){
 92             cnt+=a[j];
 93         }
 94         b[i]=cnt;
 95     }
 96     for(int i=1;i<=n;i++){
 97         int op,l,r,c;
 98         scanf("%d%d%d%d",&op,&l,&r,&c);
 99         if(op==0){
100             update(l,r);
101 //            for(int i=1;i<=n;i++)
102 //                cout<<a[i]<<" ";
103 //            cout<<endl;
104         }
105         else{
106             printf("%lld
",query(l,r));
107         }
108     }
109 }
110 
111 
112 /*
113 10
114 1 3 4 2 5 7 11 3 5 1
115 0 1 5 1
116 1 1 7 2
117 0 3 9 1
118 1 4 8 7
119 1 1 10 6
120 1 3 5 3
121 1 5 10 7
122 1 6 10 6
123 1 2 7 4
124 1 3 7 5
125 
126 25
127 8
128 14
129 3
130 10
131 9
132 9
133 8
134 */

LOJ #6281. 数列分块入门 5-分块(区间开方、区间求和)

#6281. 数列分块入门 5

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示