发布时间：2024-06-07

分块

思想

• 维护块内信息，一般块长选取 $\sqrt n$
• 如果是区间查询，如果在完整的块中，直接暴力
• 不完整，拆分成左边不完整，中间若干个完整，右边不完整
• 时间复杂度: $O(\sqrt n)$

习题

P2801 教主的魔法

题意：

• M L R C,对区间加C
• A L R C,查询区间大于等于C的个数

int e[N];//数组副本
int L[N],R[N];//L[i],R[i]表示编号为i的左右边界
int be[N];//be[i]表示i属于第几块
int a[N];
int tot,tag[N];//tag为信息
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    auto cal=[&](int k){//重构第k个块
        for(int i=L[k];i<=R[k];i++)e[i]=a[i];
        sort(e+L[k],e+R[k]+1);
    };
    int block=sqrt(n);
    tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){//分块
        L[i]=(i-1)*block+1,R[i]=min(i*block,n);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
        cal(i);
    }
    while(q--){
        char op;
        int l,r,c;
        cin>>op>>l>>r>>c;
        if(op=='M'){
            if(be[l]==be[r]){
                for(int i=l;i<=r;i++)a[i]+=c;
                cal(be[l]);
                continue;
            }
            for(int i=l;i<=R[be[l]];i++)a[i]+=c;
            for(int i=L[be[r]];i<=r;i++)a[i]+=c;
            cal(be[l]);
            cal(be[r]);
            for(int i=be[l]+1;i<=be[r]-1;i++)tag[i]+=c;
            continue;
        }
        int ans=0;
        if(be[l]==be[r]){
            for(int i=l;i<=r;i++)ans+=(a[i]+tag[be[i]]>=c);
            cout<<ans<<"\n";
            continue;
        }
        for(int i=l;i<=R[be[l]];i++)ans+=(a[i]+tag[be[i]]>=c);
        for(int i=L[be[r]];i<=r;i++)ans+=(a[i]+tag[be[i]]>=c);
        for(int i=be[l]+1;i<=be[r]-1;i++){
            ans+=e+R[i]+1-lower_bound(e+L[i],e+R[i]+1,c-tag[i]);
        }
        cout<<ans<<"\n";
    }
}

CF1942F Farmer John's Favorite Function

题意：
给定长度为n的数组a，定义函数：

• $f_1= \sqrt a_1$
• $f_i= \sqrt {f_{i-1}+a_i}$
• q次操作，每次给定k x，修改a[k]=x

思路：

• 显然f[i]<2e9
• 如果k与n大于等于6，那么影响只会是0或1

LL e[N],L[N],R[N],a[N],f[N],be[N];
//e为块内初始值为0算出来的值
//f为该块最后一个元素加1，倒推算出来的值，如果当前算出来的ans>=初值，则ans+1
LL kf(LL n){
    LL x=sqrtl(n);
    while(x*x>n)x--;
    while((x+1)*(x+1)<=n)x++;
    return x;
}
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    int block=max(10,(int)sqrt(n)),tot=(n+block-1)/block;
    auto cg=[&](int k){
        if(k==tot)return;
        e[k]=0;
        for(int i=L[k];i<=R[k];i++)e[k]=kf(e[k]+a[i]);
        f[k]=e[k]+1;
        for(int i=R[k];i>=L[k]&&f[k]!=INF;i--)f[k]=min(INF,f[k]*f[k]-a[i]);
    };
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
        cg(i);
    }
    while(q--){
        LL x,y;
        cin>>x>>y;
        a[x]=y;
        cg(be[x]);
        LL ans=0;
        for(int i=1;i<=tot-1;i++)ans=e[i]+(ans>=f[i]);
        for(int i=L[tot];i<=n;i++)ans=kf(ans+a[i]);
        cout<<ans<<"\n";
    }
}