P9989 分块题解 [Ynoi Easy Round 2023] TEST_69

Bingxiu · 2023-12-26 23:08:34 · 题解

一道 Ynoi 题怎能没有分块题解？

分块那么简单，为什么没人用？

前置芝士

• 分块

没了

题目解法

分块时，与别的题解不同，这里选择记录每块的覆盖标记的最大公约数来判断需不需要更新。

分成 \sqrt n 块，而每块最多 \Theta(\log V) 次（V 是值域，因为每次有实质的改变的更新都会把懒标记都变为它的一个真因子，所以至少除以 2）更新，每次更新 \Theta(\sqrt n)，每次修改需要固定的 \sqrt n 次遍历块，加上对块的修改。

所以总时间复杂度 \Theta(n\sqrt n \log V+m\sqrt n)，居然过了。

发题解的时候复杂度写错了，总时间复杂度应该是 \Theta(\sqrt n \times \sqrt n \times \log V+m \sqrt n)=\Theta(n \log V+m \sqrt n)，能过。

代码实现中使用了 0 \sim n-1 下标（为了分块方便写代码），注意一下细节（long long）就好了。

AC code：

#include<bits/stdc++.h>
using namespace std;
int n,m,o,l,r,u,v,f=448;
long long a[200009],e,d[449],x;
unsigned s[449],ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>n>>m;
    for(int i=0;i<n;++i) cin>>a[i],s[i/f]+=a[i];
    for(int i=0;i<m;++i){
        cin>>o>>l>>r,--l,--r,u=l/f+1,v=r/f;
        if(u>v){
            if(o==1){cin>>x;if(d[v]!=1) for(int i=l;i<=r;++i) if(a[i]>1) e=__gcd(a[i],x),s[v]+=e-a[i],a[i]=e;}
            else if(d[v]!=1){
                ans=0;
                for(int i=l;i<=r;++i) ans+=a[i];
                cout<<ans<<"\n";
            }
            else cout<<r-l+1<<"\n";
        }
        else{
            if(o==2){
                ans=0;
                if(d[u-1]!=1) for(int j=l,_=u*f;j<_;++j) ans+=a[j];
                else ans+=u*f-l;
                if(d[v]!=1) for(int j=v*f;j<=r;++j) ans+=a[j];
                else ans+=r-v*f+1;
                for(int j=u;j<v;++j) if(d[j]!=1) ans+=s[j];else ans+=f;
                cout<<ans<<"\n";
            }
            else{
                cin>>x;
                if(d[u-1]!=1) for(int j=l,_=u*f;j<_;++j) if(a[j]>1) e=__gcd(a[j],x),s[u-1]+=e-a[j],a[j]=e;
                if(d[v]!=1) for(int j=v*f;j<=r;++j) if(a[j]>1) e=__gcd(a[j],x),s[v]+=e-a[j],a[j]=e;
                for(int j=u;j<v;++j) if(!d[j]||x%d[j]){
                    d[j]=__gcd(d[j],x);
                    if(d[j]!=1) for(int k=j*f,_=k+f;k<_;++k) if(a[k]>1) e=__gcd(a[k],x),s[j]+=e-a[k],a[k]=e;
                }
            }
        }
    }
    return 0;
}