分块大暴力

日志

• 2023/12/15 开始施工。

序列分块

P2801 教主的魔法

简要题意：给一个数组 \(a\)，区间加、区间查询 \(\ge v\) 的 \(a_i\) 的个数。\(n\le 10^6,m\le 3000\)。

这个东西类似区间加、区间 rank，显然没有 log 算法，考虑分块，设块长为 \(B\)。

对于每个块维护原数组 \(a\)、懒标记 \(add_i\)、数组 \(a\) 排序后的数组 \(b\)。

对于询问操作：整块直接二分查询，散块直接暴力查询，时间复杂度 \(O(\frac{n}{B}\log B+B)\)。

对于区间加：整块直接打上懒标记，散块直接暴力修改，然后对该块的数组 \(b\) 重构，可以直接排序，时间复杂度 \(O(B\log B+\frac{n}{B})\)，也可以用归并排序 \(O(B+\frac{n}{B})\) 解决。

\(B\) 可以取 \(\sqrt{n}\)，也可以取 \(\sqrt{n\log n}\)。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+11;
int a[N], b[N], blen, id[N], L[N], R[N], n, Q, Tag[N];
void change(int x, int y, int v){
    if(id[x]==id[y]){
        for(int i=x; i<=y; i++) a[i]+=v;
        for(int i=L[id[x]]; i<=R[id[x]]; i++) b[i]=a[i];
        sort(b+L[id[x]], b+R[id[x]]+1);
        return;
    }
    int l=x, r=R[id[x]];
    for(int i=l; i<=r; i++) a[i]+=v;
    for(int i=L[id[x]]; i<=R[id[x]]; i++) b[i]=a[i];
    sort(b+L[id[x]], b+R[id[x]]+1);
    l=L[id[y]], r=y;
    for(int i=l; i<=r; i++) a[i]+=v;
    for(int i=L[id[y]]; i<=R[id[y]]; i++) b[i]=a[i];
    sort(b+L[id[y]], b+R[id[y]]+1);
    for(int i=id[x]+1; i<id[y]; i++) Tag[i]+=v;
}
int Query(int x, int y, int v){
    int ans=0;
    if(id[x]==id[y]){
        v-=Tag[id[x]];
        for(int i=x; i<=y; i++) ans+=a[i]>=v;
        return ans;
    }
    int l=x, r=R[id[x]];
    for(int i=l; i<=r; i++) ans+=(v<=Tag[id[x]]+a[i]);
    l=L[id[y]], r=y;
    for(int i=l; i<=r; i++) ans+=(v<=Tag[id[y]]+a[i]);
    for(int i=id[x]+1; i<id[y]; i++)
        ans+=(b+R[i]+1)-lower_bound(b+L[i], b+R[i]+1, v-Tag[i]);
    return ans;
}
int main(){
    scanf("%d %d", &n, &Q);
    blen=max(2, (int)sqrt(n+0.5));
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        b[i]=a[i];
        id[i]=(i-1)/blen+1;
        if(!L[id[i]]) L[id[i]]=i;
        R[id[i]]=i;
    }
    for(int i=1; i<=id[n]; i++)
        sort(b+L[i], b+R[i]+1);
    while(Q--){
        char op;
        int l, r, v;
        scanf(" %c %d %d %d", &op, &l, &r, &v);
        if(op=='M')change(l, r, v);
        else printf("%d\n", Query(l, r, v));
    }
    return 0;
}

P5356 [Ynoi2017] 由乃打扑克

考虑分块，维护每个块的懒标记，并对每个块排序得到数组 \(b\)。

• 对于询问，二分答案 \(k\)，问题转化为教主的魔法，对于整块直接二分查询，散块则是提前归并排序，然后二分查询。
• 对于修改，散块可以归并排序 \(O(B)\) 对数组 \(b\) 重构，也可以直接 sort，整块直接打标记即可。

关于卡常：二分查询有多少个数 \(\le v\) 时,若 \(\min > v\) 则直接返回 \(0\)，若 \(\max\le v\) 则直接返回该块长。其他的看代码。

// qwq
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+9;
int a[N],b[N],add[N],id[N];
int L[N],R[N],n,m,B,Bc,tmp[N];
inline bool cmp(const int &x,const int &y){
    return a[x]<a[y];
}
inline int Q(int idx,int w){
    int l=L[idx],r=R[idx],ans=r+1;
    if(w<=a[b[l]])return r-l+1;
    if(w>a[b[r]])return 0;
    while(l<=r){
        int mid=l+r>>1;
        if(a[b[mid]]>=w)ans=mid,r=mid-1;
        else l=mid+1;
    }
    return R[idx]-ans+1;
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m,B=150,Bc=(n-1)/B+1;
    for(int i=1;i<=n;i++){
        cin>>a[i],b[i]=i,id[i]=(i-1)/B+1;
        R[id[i]]=i,!L[id[i]]&&(L[id[i]]=i);
    }
    for(int i=1;i<=Bc;i++)sort(b+L[i],b+R[i]+1,cmp);
    while(m--){
        int opt,l,r,k;
        cin>>opt>>l>>r>>k;
        if(opt==2){ // O(BlogB)
            if(id[l]==id[r]){
                for(int i=l;i<=r;i++)a[i]+=k;
                sort(b+L[id[l]],b+R[id[l]]+1,cmp);
            }else{
                for(int i=l;id[i]==id[l];i++)a[i]+=k;
                for(int i=r;id[i]==id[r];i--)a[i]+=k;
                for(int i=id[l]+1;i<id[r];i++)add[i]+=k;
                sort(b+L[id[l]],b+R[id[l]]+1,cmp);
                sort(b+L[id[r]],b+R[id[r]]+1,cmp);
            }
        }else{
            if(r-l+1<k||k<1){
                cout<<"-1\n";
                continue;
            }
            static int tc=0; tc=0;
            if(id[l]==id[r]){ // O(B)
                for(int i=L[id[l]];i<=R[id[l]];i++){
                    k-=(b[i]>=l&&b[i]<=r);
                    if(!k){cout<<a[b[i]]+add[id[l]]<<'\n';break;}
                }
            }else{// O(BlogVlogB)
                k=r-l+1-k+1;
                int I=L[id[l]],J=L[id[r]];
                while(I<=R[id[l]]&&J<=R[id[r]]){
                    if(a[b[I]]+add[id[I]]<=a[b[J]]+add[id[J]])
                         (b[I]>=l&&b[I]<=r)&&(tmp[++tc]=a[b[I]]+add[id[I]]),I++;
                    else (b[J]>=l&&b[J]<=r)&&(tmp[++tc]=a[b[J]]+add[id[J]]),J++;
                }
                while(I<=R[id[l]]) (b[I]>=l&&b[I]<=r)&&(tmp[++tc]=a[b[I]]+add[id[I]]),I++;
                while(J<=R[id[r]])(b[J]>=l&&b[J]<=r)&&(tmp[++tc]=a[b[J]]+add[id[J]]),J++;
                if(id[l]+1==id[r]){
                    cout<<tmp[tc-k+1]<<'\n';
                    continue;
                }
                int al=INT_MAX,ar=INT_MIN,ans=0,mid,num;
                tc&&(ar=max(tmp[tc],ar),al=min(tmp[1],al));
                for(int i=id[l]+1;i<id[r];i++)
                    ar=max(ar,a[b[R[i]]]+add[i]),al=min(al,a[b[L[i]]]+add[i]);
                if(k==1){
                    cout<<ar<<'\n';
                    continue;
                }
                if(k==r-l+1){
                    cout<<al<<'\n';
                    continue;
                }
                while(al<=ar){
                    mid=((long long)al+ar)>>1,num=tc-(lower_bound(tmp+1,tmp+tc+1,mid)-tmp)+1;
                    for(int i=id[l]+1;i<id[r];i++)num+=Q(i,mid-add[i]);
                    if(num>=k)ans=mid,al=mid+1;
                    else ar=mid-1;
                }
                cout<<ans<<'\n';
            }
        }
    }
    cerr<<"Fine\n";
    return 0;
}

P5063 [Ynoi2014] 置身天上之森

对于每个线段树节点按照长度分类，显然只有 \(O(\log n)\) 种不同的分类，并分别用分块维护，然后用类似 教主的魔法 的方法维护即可，时间复杂度是 \(O(n\sqrt{n}\log n)\) 而不是 \(O(n\sqrt{n}\log^2 n)\)，因为 \(\sum_{i}\sqrt{\frac{n}{2^i}}\log(\frac{n}{2^i})\) 就是 \(O(\sqrt{n})\) 带上一些常数，通过调整块长可以做到 \(O(n\sqrt{n\log n})\) 。

// qwq
#include <bits/stdc++.h>
#define RG register int
#define inl inline
#define gc getchar()
using namespace std;
inline int in();
typedef long long ll;
bool M1;
constexpr int N=1e5+9,M=509;
struct node{
    int l,r;
    inl bool operator < (const node &b)const{
        return l<b.l;
    }
};
int tmp[N<<3];
inline int JJ(int l,int r,int x,int y){
    return l=max(l,x),r=min(r,y),max(0,r-l+1);
}
struct Block{
    ll *a,add[M]; int *b,*id,L[M],R[M],n,B; node *p;
    // 初始化
    inl void init(int _n,ll *_a,int *_b,int *_id,node *_p){
        n=_n,B=sqrt(n)+6,a=_a,b=_b,id=_id,p=_p;
        for(RG i=1;i<=n;i++){
            id[i]=(i-1)/B+1,R[id[i]]=i,a[i]=0;
            !L[id[i]]&&(L[id[i]]=i),b[i]=i;
        }
        for(RG i=1;i<=id[n];i++)add[i]=0;
        //for(RG i=1;i<=n;i++)cout<<p[i].l<<' '<<p[i].r<<' '<<p[i].r-p[i].l+1<<'\n';
        //for(RG i=1;i<n;i++)assert(p[i].r<p[i+1].l);
        //puts("-----------------------------");
    }
    // 单点修改 O(B)
    inl void modify1(RG x,ll v){
        a[x]+=v;
        if(v>0){
            for(RG i=L[id[x]];i<R[id[x]];i++)
                if(a[b[i]]>a[b[i+1]])swap(b[i],b[i+1]);
        }else{
            for(RG i=R[id[x]];i>L[id[x]];i--)
                if(a[b[i]]<a[b[i-1]])swap(b[i],b[i-1]);
        }
        //for(RG i=L[id[x]];i<R[id[x]];i++)
        //    assert(a[b[i]]<=a[b[i+1]]);
    }
    // 散块修改
    inl void Small(RG l,RG r,ll v){
        RG I=L[id[l]],J=L[id[l]],rm=R[id[l]],tc=0;
        while(I<=rm&&J<=rm){
            if(a[b[I]]<a[b[J]]+v)
                (b[I]< l||b[I]> r)&&(tmp[++tc]=b[I]),I++;
            else
                (b[J]>=l&&b[J]<=r)&&(tmp[++tc]=b[J]),J++;
        }
        while(I<=rm)(b[I]< l||b[I]> r)&&(tmp[++tc]=b[I]),I++;
        while(J<=rm)(b[J]>=l&&b[J]<=r)&&(tmp[++tc]=b[J]),J++;
        //assert(tc==R[id[l]]-L[id[l]]+1);
        for(RG i=1;i<=tc;i++)b[L[id[l]]+i-1]=tmp[i];
        for(RG i=l;i<=r;i++)a[i]+=v;
    }
    // 区间修改
    inl void modify2(RG l,RG r,ll v){
        if(id[l]==id[r])return Small(l,r,v);
        L[id[l]]!=l&&(Small(l,R[id[l]],v),l=R[id[l]]+1);
        R[id[r]]!=r&&(Small(L[id[r]],r,v),r=L[id[r]]-1);
        //assert(L[id[l]]==l&&R[id[r]]==r);
        for(RG i=id[l];i<=id[r];i++)add[i]+=v;
    }
    // 整块查询
    inl int Q(RG k,ll v){
        v-=add[k];
        if(a[b[L[k]]]>v)return 0;
        if(a[b[R[k]]]<=v)return R[k]-L[k]+1;
        RG l=L[k],r=R[k],ans=l-1;
        while(l<=r){
            RG mid=(l+r)>>1;
            if(a[b[mid]]<=v)ans=mid,l=mid+1;
            else r=mid-1;
        }
        return ans-L[k]+1;
    }
    // 区间查询
    inl int qr(RG l,RG r,ll v){
        RG ans=0;
        if(id[l]==id[r]){
            for(RG i=l;i<=r;i++)
                ans+=(a[i]+add[id[i]]<=v);
            return ans;
        }
        for(RG i=l;id[i]==id[l];i++) ans+=(a[i]+add[id[i]]<=v);
        for(RG i=r;id[i]==id[r];i--) ans+=(a[i]+add[id[i]]<=v);
        for(RG i=id[l]+1;i<id[r];i++)ans+=Q(i,v);
        return ans;
    }
    // -----------------------------
    // 查找位置
    inl int find(int s){
        RG l=1,r=n,ans=r;
        while(l<=r){
            RG mid=(l+r)>>1;
            if(p[mid].r>=s)ans=mid,r=mid-1;
            else l=mid+1;
        }
        return ans;
    }
    // 修改
    inl void modify(RG l,RG r,ll v){
        if(l>p[n].r||r<p[1].l||l>r)return;
        l=max(l,p[1].l),r=min(r,p[n].r);
        RG nl=find(l),nr=find(r);
        if(nl>nr)return;
        if(nl==nr){
            modify1(nl,v*JJ(l,r,p[nl].l,p[nl].r));
            return;
        }
        modify1(nl,v*JJ(l,r,p[nl].l,p[nl].r)),nl++;
        modify1(nr,v*JJ(l,r,p[nr].l,p[nr].r)),nr--;
        if(nl<=nr)modify2(nl,nr,v*(p[1].r-p[1].l+1));
    }
    // 查询
    inl ll query(RG l,RG r,ll v){
        if(l>p[n].r||r<p[1].l||l>r)return 0;
        l=max(l,p[1].l),r=min(r,p[n].r);
        if(l>r)return 0;
        RG nl=find(l),nr=find(r);
        if(nl>nr)return 0;
        if(JJ(l,r,p[nl].l,p[nl].r)!=p[nl].r-p[nl].l+1)++nl;
        if(JJ(l,r,p[nr].l,p[nr].r)!=p[nr].r-p[nr].l+1)--nr;
        return nl<=nr?qr(nl,nr,v):0;
    }
}blk[40];
ll _a[N<<3]; int _b[N<<3]; int _id[N<<3]; node _p[N<<3];
int n,m,vt,mx;
inl bool cmp(const node &x,const node &y){
    if(x.r-x.l!=y.r-y.l)return x.r-x.l>y.r-y.l;
    return x.l<y.l;
}
inl void build(RG k,RG l,RG r){
    _p[++mx]={l,r};
    if(l==r)return;
    RG mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
bool M2;
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    cerr<<1.*((&M2)-(&M1))/1024./1024.<<'\n';
    n=in(),m=in(),build(1,1,n);
    sort(_p+1,_p+mx+1,cmp);
    for(RG i=1,j;_p[i].l;i++){
        j=i;
        while(_p[j+1].r-_p[j+1].l==_p[i].r-_p[i].l&&_p[j+1].l)j++;
        ++vt,blk[vt].init(j-i+1,&_a[i-1+vt*2],&_b[i-1+vt*2],&_id[i-1+vt*2],&_p[i-1]);
        i=j;
    }
    while(m--){
        int op=in(),l=in(),r=in(),a=in();
        if(op==1){
            for(int i=1;i<=vt;i++)
                blk[i].modify(l,r,a);
        }else{
            ll ans=0;
            for(int i=1;i<=vt;i++)
                ans+=blk[i].query(l,r,a);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
inl int in(){
    char c; int x=0,bo=0;
    while(c=gc,c<'0'||c>'9')if(c=='-')bo=1;
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=gc;
    return bo?-x:x;
}

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

区间逆序对，强制在线，考虑分块，散块可以直接归并排序统计答案，对每个整块 \(i\) 维护 \(f_{i,j}\) 表示 \([1,j]\) 和块 \(i\) 之间的逆序对数，考虑方向，可以 \(O(n\sqrt{n})\) 预处理，然后询问时对每个整块计算贡献，单次询问 \(O(n\sqrt{n})\)，由于预处理的复杂度为 \(O(n\sqrt{n})\)，所以要将块长调大。

// qwq
#include <bits/stdc++.h>
using namespace std;
#define RG register int
typedef long long ll;
namespace Input{
    char buf[1<<20],*b1=buf,*b2=buf;
    #define gc (((b1==b2)&&(b2=(b1=buf)+fread(buf,1,1<<20,stdin),b1==b2))?EOF:*b1++)
    inline int in(){
        char c; int x=0; while(c=gc,c<'0'||c>'9');
        while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc;
        return x;
    }
    inline ll inll(){
        char c; ll x=0; while(c=gc,c<'0'||c>'9');
        while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc;
        return x;
    }
}using Input::in; using Input::inll;
constexpr int N=1e5+9,M=N/220+2;
int n,m,a[N],b[N],id[N],L[N],R[N],B,pre[N],suf[N];
ll f[N][M];
struct BIT{
    int c[N],cnt;
    inline void Add(RG x){
        ++cnt;
        for(;x<=n;x+=x&-x)
            c[x]++;
    }
    inline int Q(RG x){
        RG res=0;
        for(;x;x-=x&-x)
            res+=c[x];
        return res;
    }
    inline int Small(RG x){return Q(x-1);}
    inline int Big(RG x){return cnt-Q(x);}
    inline void cls(){memset(c,0,(n+2)<<2);cnt=0;}
}Tr;
inline int calc(RG x,RG y,RG l,RG r){
    if(x>y||l>r)return 0;
    RG I=L[id[x]],J=L[id[l]],ic=y-x+1,cur=0;
    while(I<=R[id[x]]&&J<=R[id[l]]){
        if(a[b[I]]<a[b[J]])
            ic-=(b[I]>=x&&b[I]<=y),I++;
        else
            (b[J]>=l&&b[J]<=r)&&(cur+=ic),J++;
    }
    return cur;
}
int main(){
    n=in(),m=in(),B=432;
    for(int i=1;i<=n;i++){
        a[i]=in(),id[i]=(i-1)/B+1,R[id[i]]=i;
        !L[id[i]]&&(L[id[i]]=i);
    }
    for(int i=1;i<=id[n];i++){
        memset(b,0,(n+2)<<2);
        for(RG j=L[i];j<=R[i];j++)b[a[j]]++;
        for(RG j=1;j<=n;j++)b[j]+=b[j-1];
        for(RG j=1;j<L[i];j++)f[j][i]=f[j-1][i]+b[a[j]];
        for(RG j=n;j>R[i];j--)f[j][i]=f[j+1][i]+(R[i]-L[i]+1)-b[a[j]];

        Tr.cls();Tr.Add(a[L[i]]);
        for(RG j=L[i]+1;j<=R[i];j++)pre[j]=pre[j-1]+Tr.Big(a[j]),Tr.Add(a[j]);

        Tr.cls(),Tr.Add(a[R[i]]);
        for(RG j=R[i]-1;j>=L[i];j--)suf[j]=suf[j+1]+Tr.Small(a[j]),Tr.Add(a[j]);
    }
    for(RG i=1;i<=n;i++)b[i]=i;
    for(RG i=1;i<=id[n];i++)
        sort(b+L[i],b+R[i]+1,[=](int x,int y){
            return a[x]<a[y];
        });
    ll ans=0;
    while(m--){
        int l=inll()^ans,r=inll()^ans;
        if(id[l]==id[r]){
            if(l==L[id[l]])ans=pre[r];
            else ans=pre[r]-pre[l-1]-calc(L[id[l]],l-1,l,r);
        }else{
            ans=suf[l]+pre[r]+calc(l,R[id[l]],L[id[r]],r);
            for(RG i=id[l]+1;i<id[r];i++){
                ans+=pre[R[i]]+f[L[i]-1][i]-f[l-1][i];
                ans+=f[L[id[r]]][i]-f[r+1][i];
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II （二次离线）

区间逆序对，先考虑莫队，显然用树状数组做到 \(O(q\sqrt{n}\log n)\) 的复杂度，考虑将 \(\log n\) 去掉。

设 \([l,r]\times[x,y]\) 表示 \([l,r]\) 和 \([x,y]\) 之间的逆序对数。

考虑从区间 \([l,r]\) 移动到 \([l,r']\)（\(r<r'\)）会对答案产生什么贡献，其他情况同理：

显然 \(\sum_{i=r+1}^{r'}[1,i-1]\times[i,i]\) 可以预处理，\(\sum_{i=r+1}^{r'}[1,l-1]\times[i,i]\) 可以再次离线并挂在 \(l-1\) 处查询，用分块维护， \(O(\sqrt{n})\) 修改、\(O(1)\) 询问即可做到 \(O((q+n)\sqrt{n})\) 的时间复杂度，空间复杂度为 \(O(n+q)\)。

// qwq
#include <bits/stdc++.h>
#define RG register int
using namespace std;
constexpr int N=2e5+9,M=509;
int id[N];
struct data{
    int a[N],f[M],sum,n,B;
    void init(int _n){
        B=sqrt(n=_n)+2;
        for(int i=1;i<=n;i++)
            id[i]=(i-1)/B+1;
    }
    void cls(){
        sum=0;for(int i=0;i<=n;i++)a[i]=0;
        for(int i=0;i<=id[n]+1;i++)f[i]=0;
    }
    inline void add(int x,int v){
        for(RG i=x;id[i]==id[x];i++)a[i]+=v;
        for(RG i=id[x];i<=id[n];i++)f[i]+=v;
        sum+=v;
    }
    inline int Pre(int x){return x?a[x]+f[id[x]-1]:0;}
    inline int Small(int x){return Pre(x-1);}
    inline int Big(int x){return sum-Pre(x);}
}K;
typedef long long ll;
struct qy{int l,r,id;}q[N];
struct qt{int l,r,v,id;};
int n,m,a[N],b[N];
ll ans[N],_p[N],_s[N];
vector<qt>_1[N],_2[N];
void init1(){
    cin>>n>>m,K.init(n);
    for(RG i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    for(RG i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(RG i=1;i<=n;i++){
        _p[i]=_p[i-1]+K.Big(a[i]);
        K.add(a[i],1);
    }
    K.cls();
    for(RG i=n;i>=1;i--){
        _s[i]=_s[i+1]+K.Small(a[i]);
        K.add(a[i],1);
    }
}
bool cmp(const qy &x,const qy &y){
    if(id[x.l]^id[y.l])return x.l<y.l;
    return (id[x.l]&1)?x.r<y.r:x.r>y.r;
}
void init2(){
    for(RG i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+m+1,cmp),q[0]={1,1,0};
    for(RG i=1;i<=m;i++){
        RG pl=q[i-1].l,pr=q[i-1].r,l=q[i].l,r=q[i].r;
        if(pr<r){
            ans[q[i].id]+=_p[r]-_p[pr];
            _1[pl-1].push_back({pr+1,r,-1,q[i].id});
        }
        else if(pr>r){
            ans[q[i].id]-=(_p[pr]-_p[r]);
            _1[pl-1].push_back({r+1,pr,1,q[i].id});
        }
        pr=r;
        if(l<pl){
            ans[q[i].id]+=(_s[l]-_s[pl]);
            _2[pr+1].push_back({l,pl-1,-1,q[i].id});
        }
        else if(l>pl){
            ans[q[i].id]-=_s[pl]-_s[l];
            _2[pr+1].push_back({pl,l-1,1,q[i].id});
        }
    }
}
void sol(){
    K.cls();
    for(int i=1;i<=n;i++){
        K.add(a[i],1);
        for(auto idx:_1[i]){
            ll tmp=0;
            for(int j=idx.l;j<=idx.r;j++)
                tmp+=K.Big(a[j]);
            ans[idx.id]+=tmp*idx.v;
        }
    }
    K.cls();
    for(int i=n;i>=1;i--){
        K.add(a[i],1);
        for(auto idx:_2[i]){
            ll tmp=0;
            for(int j=idx.l;j<=idx.r;j++)
                tmp+=K.Small(a[j]);
            ans[idx.id]+=tmp*idx.v;
        }
    }
    for(int i=1;i<=m;i++)
        ans[q[i].id]+=ans[q[i-1].id];
}
int main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init1(),init2(),sol();
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<endl;
    return 0;
}

根号分治

P5309 [Ynoi2011] 初始化

神仙题，设 \(B=\sqrt{n}\)，考虑对 \(y\) 是否小于 \(B\) 进行分类讨论：

1. 当 \(x\ge B\) 时，最多只会修改 \(\frac{n}{B}\) 处，直接暴力修改即可，这里使用分块维护，做到 \(O(1)\) 的单点修改，\(O(\sqrt{n})\) 询问，以保证修改的时间复杂度。
2. 当 \(x< B\) 时，考虑对序列分块，块长为 \(x\)，因为 \(y\le x\)，所以修改会对所有块产生贡献，单独考虑贡献，对于一个询问，将其按块长 \(x\) 进行分块，对于一个整块，所有修改都会有贡献，对于散块则是前缀或后缀产生贡献，所以对于每个 \(x\)，维护 \(y\) 的前后缀和即可，因为 \(x<B\)，所以可以 \(O(B)\) 更新，\(O(1)\) 询问一个 \(x\) 对答案的贡献。

// qwq
#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
typedef long long ll;
constexpr int N=2e5+99,mo=1e9+7;
int n,m,id[N],L[N],R[N],B,BB;
ll S[666][666],a[N],b[N];
inline void in(int &x){
    char c; x=0;
    while(c=gc,c<'0'||c>'9');
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=gc;
}
int main(){
    in(n),in(m),BB=sqrt(n)+2,B=pow(n,0.375)+2;
    for(int i=1,x;i<=n;i++){
        in(x),(b[id[i]=(i-1)/BB+1]+=(a[i]=x))%=mo;
        R[id[i]]=i,!L[id[i]]&&(L[id[i]]=i);
    }
    while(m--){
        int op;in(op);
        if(op==1){
            int x,y,z;
            in(x),in(y),in(z);
            if(x>B){
                for(int i=y;i<=n;i+=x)
                    a[i]+=z,b[id[i]]+=z;
            }else{
                for(int i=y%x;i<x;i++)
                    S[x][i]+=z;
            }
        }else{
            int l,r; ll sum=0; in(l),in(r);
            if(id[l]==id[r]){
                for(int i=l;i<=r;i++)sum+=a[i];
            }else{
                for(int i=l;id[i]==id[l];i++)sum+=a[i];
                for(int i=r;id[i]==id[r];i--)sum+=a[i];
                for(int i=id[l]+1;i<id[r];i++)sum+=b[i];
            }
            for(int X=1;X<=B;X++){
                sum+=(ll)(S[X][X-1]%mo)*(r/X-l/X);
                sum+=S[X][r%X]-((l%X)?S[X][(l%X)-1]:0);
            }
            printf("%d\n",(sum%mo+mo)%mo);
        }
    }
    return 0;
}

P3591 [POI2015] ODW

暴力一：对于一次行走，直接暴力统计，单次时间复杂度为 \(O(n)\)。

暴力二：对于一次行走，直接预处理从点 \(u\) 一直向上走 \(i\) 步的答案 \(f_{u,i}\)，可以做到 \(O(\log n)\) 的单次查询，但是预处理的复杂度为 \(O(n^2)\)。

考虑将两个暴力合并在一起，对于 \(k\ge B\)，跑暴力一，否则 \(O(n\sqrt{n})\) 预处理，\(O(\log n)\) 查询。

对于暴力一，我们要用树剖，而不是倍增，因为树剖只会跳 \(\log n\) 次链，所以时间复杂度最高为 \(\sqrt{n}\)，而倍增是 \(\sqrt{n}\log n\) 的复杂度。

// qwq
#include <bits/stdc++.h>
using namespace std;
constexpr int N=5e4+9,M=230;
int dep[N],Fa[N],sz[N],ms[N],st[N][M],dr[N][M],B;
int top[N],dfn[N],vt[N],dft,n,m,val[N];
vector<int>e[N];
inline void dfs1(int u,int fa){
    for(int i=2;i<=B;i++)st[u][i]=st[fa][i-1];
    Fa[u]=fa,dep[u]=dep[fa]+1,sz[u]=1,st[u][1]=fa;
    for(int i=1;i<=B;i++)dr[u][i]=val[u]+dr[st[u][i]][i];
    for(int v:e[u])if(v^fa){
        dfs1(v,u),sz[u]+=sz[v];
        if(sz[v]>sz[ms[u]])ms[u]=v;
    }
}
inline void dfs2(int u,int Top){
    top[u]=Top,vt[dfn[u]=++dft]=u;if(ms[u])dfs2(ms[u],Top);
    for(int v:e[u])if(v!=Fa[u]&&v!=ms[u])dfs2(v,v);
}
inline int lca(int u,int v){
    while(top[u]^top[v]){
        if(dep[top[u]]<=dep[top[v]])swap(u,v);
        u=Fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
inline int jump(int x,int d){
    while(x){
        int dr=dfn[x]-dfn[top[x]];
        if(dr>=d)return vt[dfn[x]-d];
        d-=(dr+1);x=Fa[top[x]];
    }
    return 0;
}
inline int Big(int x,int y,int k){
    int l=lca(x,y),ans=0;
    while(dep[x]>dep[l])
        ans+=val[x],x=jump(x,k);
    while(dep[y]>dep[l])
        ans+=val[y],y=jump(y,k);
    if(x==l&&y==l)ans+=val[x];
    return ans;
}
inline int Small(int x,int y,int k){
    int l=lca(x,y),d,ans=0,nx,ny;
    nx=jump(x,d=((dep[x]-dep[l])/k)*k);
    ans+=dr[x][k]-dr[nx][k];
    ny=jump(y,d=((dep[y]-dep[l])/k)*k);
    ans+=dr[y][k]-dr[ny][k];
    ans+=val[nx]+val[ny];
    nx==ny&&(ans-=val[nx]);
    return ans;
}
#define gc getchar()
inline int in(){
    char c;int x=0;
    while(c=gc,c<'0'||c>'9');
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=gc;
    return x;
}
int p[N];
int main(){
    n=in(),B=sqrt(n);
    for(int i=1;i<=n;i++)val[i]=in();
    for(int i=1,x,y;i<n;i++)
        e[x=in()].push_back(y=in()),
        e[y].push_back(x);
    dfs1(1,0),dfs2(1,1);
    for(int i=1;i<=n;i++)p[i]=in();
    for(int i=1,k;i<n;i++){
        if((k=in())>B)cout<<Big(p[i],p[i+1],k)<<'\n';
        else    cout<<Small(p[i],p[i+1],k)<<'\n';
    }
    return 0;
}

P5397 [Ynoi2018] 天降之物

考虑根号分治，对于每个出现次数大于 \(B\) 的数 \(k\)，预处理出 \(k\) 和其他数的答案数组 \(f\)，这个的时间复杂度为 \(O(nB)\) 的。

对于每个小块维护其出现位置，对于每个大块维护所有加入大块的小块的出现位置，称其为附属集合，定期对附属集合重构清空，阀值为 \(B\)，显然总重构次数是 \(O(B)\) 的。这里默认小块的附属集合为其出现位置。

对于修改 x,y：

合并 \(f_{?,x}\) 和 \(f_{?,y}\)。

• 若 \(x\)、\(y\) 均为大块，则直接暴力加入并重构。

• 若 \(x\) 为小块，\(y\) 为大块，则 \(x\) 加入 \(y\) 的附属集合，超过阀值直接重构。

• 若 \(x\)、\(y\) 均为小块，则直接归并加入即可，若加入后大小大于 \(B\)，将其视为大块，并预处理其对应的 \(f\) 数组。

对于查询 x y：

归并计算附属集合的贡献，然后若其中有大块则查询 \(f\) 即可。

总时间复杂度为 \(O(n^{1.5})\)。

// qwq
#include <bits/stdc++.h>
#define RG register int
#define gc getchar()
#define ALL(X) X.begin(),X.end()
#define SIZ(X) (int(X.size()))
using namespace std;
inline void cmn(int &x,const int &y){x>y&&(x=y);}
constexpr int N=1e5+9,B=400,M=N/B+5;
inline int in(){
    char c; int x=0; while(c=gc,c<'0'||c>'9');
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc;
    return x;
}


int n,m,a[N],vt[N],id[N],Id,f[M+2][N];
vector<int>e[N];

void mvec(int x,int y){
    vector<int>res(SIZ(e[x])+SIZ(e[y]));
    merge(ALL(e[x]),ALL(e[y]),res.begin());
    e[y]=res;
}

void build(RG x){
    if(!id[x])id[x]=++Id;
    RG u=id[x];
    memset(f[u],0x3f,sizeof f[u]);
    vector<int>().swap(e[x]),f[u][x]=0;
    for(RG i=1,len=N;i<=n;i++){
        if(a[i]==x)len=0;
        else cmn(f[u][a[i]],++len);
    }
    for(RG i=n,len=N;i>=1;i--){
        if(a[i]==x)len=0;
        else cmn(f[u][a[i]],++len);
    }
}

inline void Merge(RG &x,RG &y){
    if(!x||x==y){return;} if(!y){y=x;x=0;return;}
    if(id[x])swap(x,y);
    for(RG i=1;i<=Id;i++)cmn(f[i][y],f[i][x]);
    if(id[x]){ // big - big
        for(RG i=1;i<=n;i++)if(a[i]==x)a[i]=y;
        build(y);
    }else{
        // small - (big/small)
        for(auto i:e[x])a[i]=y;
        mvec(x,y);
        if(SIZ(e[y])>=B)build(y); // 重构
    }
    vector<int>().swap(e[x]),x=0;
}

inline int Q(int x,int y){
    if(!x||!y)return -1;
    if(x==y)return 0;
    int ans=1e9;
    vector<int>res(SIZ(e[x])+SIZ(e[y]));
    merge(ALL(e[x]),ALL(e[y]),res.begin());
    for(int i=1;i<SIZ(res);i++)
        if(a[res[i]]!=a[res[i-1]])
            cmn(ans,res[i]-res[i-1]);
    if(id[x])cmn(ans,f[id[x]][y]);
    if(id[y])cmn(ans,f[id[y]][x]);
    return ans;
}

int main(){
    n=in(),m=in();
    for(int i=1;i<=n;i++)
        e[a[i]=in()].push_back(i),
        vt[a[i]]=a[i];
    for(int i=1;i<=n;i++)
        if(SIZ(e[i])>=B)
            build(i);
    int lstans=0;
    while(m--){
        int op=in(),x=in()^lstans,y=in()^lstans;
        if(op==2){
            lstans=Q(vt[x],vt[y]);
            if(lstans==-1)lstans=0,puts("Ikaros");
            else cout<<lstans<<'\n';
        }
        else Merge(vt[x],vt[y]);
    }
    return 0;
}

后记

• 分块相关杂谈 - command_block 的博客

本栏目推荐文章
• [CTSC2018]暴力写挂题解
• 分块大暴力
• SSH暴力破解排查与防御
• 家长直呼太暴力！这些算法可能会被删除
• Vue源码学习(十六):diff算法(三)暴力比对
• cf797eE. Array Queries（暴力+复杂度分析）
• cf1582F2. Korney Korneevich and XOR (hard version)（暴力优化）
• 暴力枚举
• 分块：优雅的暴力
• [CF914F] Substrings in a String（字符串的暴力匹配）

暴力非暴力 暴力ssh 暴力cadence问题16.3 暴力a-table问题table weetcode3暴力weetcode记忆 破解工具 暴力 工具medusa 算法 暴力 家长 限速 暴力 实证 暴力 机器calibre 字典 黑客 暴力pydictor