SP2713 GSS4 - Can you answer these queries IV 分块

问题描述

LG-SP2713

题解

分块，区间开根。

如果一块的最大值是 \(1\) ，那么这个块就不用开根了。

如果最大值不是 \(1\) ，直接暴力开就好了。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

int non;

const int maxn=100007;

int n,cas;
int a[maxn];
int L[maxn],R[maxn],bel[maxn];
int cnt,blo,mx[maxn],sum[maxn];

void reset(){
    memset(mx,0,sizeof(mx));
    memset(sum,0,sizeof(sum));
    memset(L,0,sizeof(L));
    memset(R,0,sizeof(R));
    memset(bel,0,sizeof(bel));
}

void Init(){
    for(int i=1;i<=n;i++) read(a[i]);
}

void change(){
    int x,y;read(x);read(y);//read(non);
    if(x>y) swap(x,y);
    if(bel[x]==bel[y]){
        if(mx[bel[x]]==1) return;
        for(int i=x;i<=y;i++){
            sum[bel[i]]-=a[i];
            a[i]=sqrt((double)a[i]);
            sum[bel[i]]+=a[i];
        }
        mx[bel[x]]=-1;
        for(int i=L[bel[x]];i<=R[bel[x]];i++)
            mx[bel[x]]=max(mx[bel[x]],a[i]);
        return;
    }
    if(mx[bel[x]]!=1){
        for(int i=x;i<=R[bel[x]];i++){
            sum[bel[i]]-=a[i];
            a[i]=sqrt((double)a[i]);
            sum[bel[i]]+=a[i];
        }
        mx[bel[x]]=-1;
        for(int i=L[bel[x]];i<=R[bel[x]];i++){
            mx[bel[x]]=max(mx[bel[x]],a[i]);
        }
    }
    if(mx[bel[y]]!=1){
        for(int i=L[bel[y]];i<=y;i++){
            sum[bel[i]]-=a[i];
            a[i]=sqrt((double)a[i]);
            sum[bel[i]]+=a[i];
        }
        mx[bel[y]]=-1;
        for(int i=L[bel[y]];i<=R[bel[y]];i++){
            mx[bel[y]]=max(mx[bel[y]],a[i]);
        }
    }
    for(int i=bel[x]+1;i<bel[y];i++){
        if(mx[i]==1) continue;
        mx[i]=-1;
        for(int j=L[i];j<=R[i];j++){
            sum[i]-=a[j];
            a[j]=sqrt((double)a[j]);
            sum[i]+=a[j];
            mx[i]=max(mx[i],a[j]);
        }
    }
}

void query(){
    int res=0,x,y;read(x);read(y);//read(non);
    if(x>y) swap(x,y);
    if(bel[x]==bel[y]){
        for(int i=x;i<=y;i++) res+=a[i];
        printf("%lld\n",res);
        return;
    }
    for(int i=x;i<=R[bel[x]];i++) res+=a[i];
    for(int i=L[bel[y]];i<=y;i++) res+=a[i];
    for(int i=bel[x]+1;i<bel[y];i++) res+=sum[i];
    printf("%lld\n",res);
}

void solve(){
    blo=sqrt((double)n);cnt=n/blo;
    cnt=cnt+((n%blo)!=0);
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*blo+1,R[i]=i*blo;
    }
    R[cnt]=n;
    for(int i=1;i<=n;i++){
        bel[i]=(i-1)/blo+1;
        sum[bel[i]]+=a[i];
        mx[bel[i]]=max(mx[bel[i]],a[i]);
    }
    int T,op;
//  T=n;
    read(T);
    while(T--){
        read(op);
        if(op==0) change();
        else query();
    }
    puts("");
}

signed main(){
    while((~scanf("%lld",&n))&&n){
        printf("Case #%d:\n",++cas);
        reset();Init();solve();
    }
    return 0;
}