题目链接:
传送门
题目分析:
题意简化: 给你一个元素非负的序列, 要求支持区间开方, 区间求和.
做法很多, 洛谷的题解里线段树 / 树状数组 / 分块 /... 都有 (基本就是数据结构的群魔乱舞), 不过分块能跑过的话分块就好了.
记录区间 \(i\) 的元素总和为 \(sum_i\), 如果 \(sum_i=R[i]-L[i]+1\) 的话说明这个区间内只有 1 了, 就不用再操作了, 否则直接暴力开方即可.
由于数据范围很小, 最多开个 10 次方上下就全都变成 1 了, 所以时间上是没有问题的.
再有一个细节要处理是数据可能包含 0(这一点洛谷保证没有 0 的数据范围顿时变得一万个良心), 所以在读入的时候如果读到 0 就把这个元素加成 1, 并另外维护一个数组记录此元素的位置, 再维护一个数组记录每个块内 0 的个数, 最后求和的时候减去即可.
数据范围很大, 不开 \(long long\) 跑不过.
代码:
- #include<bits/stdc++.h>
- #define N (200000+5)
- using namespace std;
- inline long long read(){
- long long cnt=0,f=1;char c;
- c=getchar();
- while(!isdigit(c)){
- if(c=='-') f=-f;
- c=getchar();
- }
- while(isdigit(c)){
- cnt=cnt*10+c-'0';
- c=getchar();
- }
- return cnt*f;
- }
- long long n,m,k,l,r;
- long long a[N],sum[N];
- long long L[N],R[N],pos[N];
- long long pos_of_zero[N],sum_of_zero[N];
- void Sqrt(int l,int r) {
- int p=pos[l];int q=pos[r];
- if(p==q) {
- if(sum[p]==R[p]-L[p]+1) return;
- else {
- for(register int i=l;i<=r;i++) {
- sum[p]-=a[i];
- a[i]=sqrt(a[i]);
- sum[p]+=a[i];
- }
- }
- }
- else {
- if(sum[p]>R[p]-L[p]+1) {
- for(register int i=l;i<=R[p];i++) {
- sum[p]-=a[i];
- a[i]=sqrt(a[i]);
- sum[p]+=a[i];
- }
- }
- if(sum[q]>R[q]-L[q]+1) {
- for(register int i=L[q];i<=r;i++) {
- sum[q]-=a[i];
- a[i]=sqrt(a[i]);
- sum[q]+=a[i];
- }
- }
- for(register int i=p+1;i<=q-1;i++) {
- if(sum[i]==R[i]-L[i]+1) continue;
- else {
- for(register int j=L[i];j<=R[i];j++) {
- sum[i]-=a[j];
- a[j]=sqrt(a[j]);
- sum[i]+=a[j];
- }
- }
- }
- }
- }
- long long query(int l,int r) {
- int p=pos[l];int q=pos[r];
- long long ans = 0;
- if(p==q) {
- for(register int i=l;i<=r;i++) {
- ans+=a[i];ans-=pos_of_zero[i];
- }
- }
- else {
- for(register int i=l;i<=R[p];i++) {
- ans+=a[i];ans-=pos_of_zero[i];
- }
- for(register int i=L[q];i<=r;i++) {
- ans+=a[i];ans-=pos_of_zero[i];
- }
- for(register int i=p+1;i<=q-1;i++) {
- ans+=sum[i];ans-=sum_of_zero[i];
- }
- }
- return ans;
- }
- int main(){
- n=read();
- for(register int i=1;i<=n;i++) {
- a[i]=read();
- if(a[i]==0) {
- pos_of_zero[i]=1;
- a[i]++;
- }
- }
- int t=sqrt(n);
- for(register int i=1;i<=t;i++){
- L[i]=(i-1)*t+1;
- R[i]=i*t;
- }
- if(R[t]<n) {
- ++t;
- L[t]=R[t-1]+1;
- R[t]=n;
- }
- for(register int i=1;i<=t;i++)
- for(register int j=L[i];j<=R[i];j++){
- pos[j]=i;
- sum[i]+=a[j];
- if(pos_of_zero[j]) sum_of_zero[i]++;
- }
- m=read();
- for(register int i=1;i<=m;i++) {
- k=read();l=read();r=read();
- if(l>r) swap(l,r);
- if(k==2) Sqrt(l,r);
- else printf("%lld\n",query(l,r));
- }
- return 0;
- }
[BZOJ3211] 花神游历各国
来源: http://www.bubuko.com/infodetail-2939047.html