分塊算法總結

　　分塊，就是一種暴力算法，不過複雜度優於暴力，是基於足夠的預處理和合理可行的維護操作進行優化時間，

　在預處理+維護的耗時上與暴力處理的耗時上找到一種平衡，於是出了這個優美的算法

　　標誌：查詢某一區間內元素種類數，查詢某一區間大於等於某一元素的數的個數（即排名

　　為了查詢大於等於C的個數，可以排序，用區間長度-C的排名就是 答案數。

　　所以可以動態維護一個塊內有序的數組

 

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;++i)
#define il inline 
using namespace std;
const int maxn=1000010;
vector <int> ve[1010];
int v[maxn],bl[maxn],atag[maxn];
int n,m,base;
il void reset(int x) //重新維護一個塊內元素的順序
{
    ve[x].clear();
    inc(i,(x-1)*base+1,min(x*base,n)) ve[x].push_back(v[i]);//別忘了容易溢出n的數組大小呀
    sort(ve[x].begin(),ve[x].end());
}
il void add(int a,int b,int c)//區間加
{
    inc(i,a,min(bl[a]*base,b)) v[i]+=c;//暴力處理前半部分
    reset(bl[a]);
    if(bl[a]!=bl[b]) {inc(i,(bl[b]-1)*base+1,b) v[i]+=c; reset(bl[b]);}//暴力處理後面部分
    inc(i,bl[a]+1,bl[b]-1) atag[i]+=c;
}
il int query(int a,int b,int c)//區間查詢
{
    int ans=0;
    inc(i,a,min(bl[a]*base,b)) if(v[i]+atag[bl[a]]<c) ans++; //暴力處理前部分
    if(bl[a]!=bl[b])
    {
        inc(i,(bl[b]-1)*base+1,b) if(v[i]+atag[bl[b]]<c) ans++;//暴力處理後面部分
    }
    inc(i,bl[a]+1,bl[b]-1)//對於塊來説，直接減去lazy_tag的影響
    {
        int x=c-atag[i];
        ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();//查詢第一個大於等於x的數的位置
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    base=sqrt(n);
    inc(i,1,n) scanf("%d",&v[i]),bl[i]=(i-1)/base+1,ve[bl[i]].push_back(v[i]);
    inc(i,1,bl[n]) sort(ve[i].begin(),ve[i].end());
    char s;
    re int x,y,z;
    inc(i,1,m)
    {
        s=getchar();
        while(s!='A'&&s!='M') s=getchar();
        if(s=='M')
        {
            scanf("%d %d %d",&x,&y,&z);
            add(x,y,z);
        }
        else 
        {
            scanf("%d %d %d",&x,&y,&z);
            printf("%d\n",y-x+1-query(x,y,z));
        }
    }
}

 

其他例題先咕着吧

 

然後...

莫隊

莫隊其實也是基於分塊的算法，主要是一種思想吧我認為，基於對詢問問題的離線處理按一定順序去處理問題

然後保證了暴力的複雜度

具體實現是要按左區間的塊排序，快相同的按右端點排序，保證同一個塊內複雜度O（n）,共有sqrt(n)塊

所以總複雜度 O（n*sqrt(n)）

主要用於查詢元素的種類數

模板：LuoguP2709 小B的詢問

#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
#define maxn 50005
struct query
{
    int l,r,id,pos;
//    friend bool operator < (query xx,query yy)
//    {    if(xx.pos==yy.pos) return xx.l<yy.r;    else return xx.pos<yy.pos;} //這裏是按奇偶性排序，可以先忽略
    bool operator <(const query &x) const {if(pos==x.pos)return r<x.r;
   else return pos<x.pos;} 
}a[maxn];
int b[maxn],n,m,K;ll cnt[maxn],Ans[maxn];
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return x*f;
}
int main()
{
//    freopen("testdata.in.txt","r",stdin);
//    freopen("4321.txt","w",stdout);
    n=read(); m=read(); K=read();
    int siz=(int) sqrt(n);
    for(re int i=1;i<=n;++i) b[i]=read();
    for(re int i=1;i<=m;++i)
    {
        a[i].l=read(); a[i].r=read(); a[i].id=i;
        a[i].pos=(a[i].l-1)/siz+1;
    }
    sort(a+1,a+m+1);
    int l=1,r=0; long long ans=0;
    for(re int i=1;i<=m;++i)
    {
        while(l>a[i].l) { l--; cnt[b[l]]++; ans+= 2*cnt[b[l]]-1 ;} //外拓的時候，先加減再統計
        while(r<a[i].r) { r++; cnt[b[r]]++; ans+= 2*cnt[b[r]]-1 ;}
        while(r>a[i].r) {cnt[b[r]]--; ans-= 2*cnt[b[r]]+1 ; r--; } //回溯的時候，先統計再加減
        while(l<a[i].l) {cnt[b[l]]--; ans-= 2*cnt[b[l]]+1 ; l++; }
        Ans[a[i].id]=ans;
    }
    for(re int i=1;i<=m;++i) printf("%lld\n",Ans[i]);
}

其次就是對於莫隊的修改操作了，帶修莫隊與原版的差異是多了個時間軸

把修改操作看作刪除舊的+增加新的，這種思想很多時候都用的上

也是裸暴力，只不過多關注時間軸上修改都幹了什麼，這樣查詢的時候只考慮當前時間之前的操作就好了

分塊大小為 (n*t)1/3  複雜度O((n4*t)1/3)   ->不會證

模板題 LuoguP1903 數顏色

//窩洛谷突然看不了自己提交的代碼了。。。先複製第一篇題解的把，，等哪天我想起來再更(逃

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
#define go(a,b,c) for(int a=b;a>=c;a--)
int read(){
    int a=0,f=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
    return f?-a:a;
}
const int N=10001;
int a[N],p[1000001],ans[N],divi;
struct nod{int pla,pre,suc;}cg[N];
struct node{int l,r,t,bel;}ls[N];
int cmp(node a,node b){
    if(a.l/divi!=b.l/divi)return a.l/divi<b.l/divi;
    if(a.r/divi!=b.r/divi)return a.r/divi<b.r/divi;
    return a.t<b.t; 
}
int main(){
    int n=read(),m=read(),ln=0,tn=0,l=1,r=0,t=0,num=0;
    fo(i,1,n)a[i]=read();
    fo(i,1,m){
        scanf("\n");
        if(getchar()=='R'){//如果讀入修改則記錄修改的地點，修改前的數字和修改後的數字
            ++tn;cg[tn].pla=read(),cg[tn].suc=read();
            cg[tn].pre=a[cg[tn].pla];
            a[cg[tn].pla]=cg[tn].suc;
        } 
        else ls[++ln]=(node){read(),read(),tn,ln};
    }
    divi=ceil(exp((log(n)+log(tn))/3));//分塊大小
    go(i,tn,1)a[cg[i].pla]=cg[i].pre;
    sort(ls+1,ls+ln+1,cmp);
    fo(i,1,m){
        while(ls[i].l<l)num+=!p[a[--l]]++;
        while(ls[i].l>l)num-=!--p[a[l++]];//l移動
        while(ls[i].r>r)num+=!p[a[++r]]++;
        while(ls[i].r<r)num-=!--p[a[r--]];//r移動
        while(ls[i].t<t){
            int pla=cg[t].pla;
            if(l<=pla&&pla<=r)num-=!--p[a[pla]];
            a[pla]=cg[t--].pre;
            if(l<=pla&&pla<=r)num+=!p[a[pla]]++;
        };
        while(ls[i].t>t){
            int pla=cg[++t].pla;
            if(l<=pla&&pla<=r)num-=!--p[a[pla]];
            a[pla]=cg[t].suc;
            if(l<=pla&&pla<=r)num+=!p[a[pla]]++;
        };//t移動
        ans[ls[i].bel]=num;
    }
    fo(i,1,ln)printf("%d\n",ans[i]); 
    return 0;
}

二次離線莫隊

updataing......