递归分治

例题¶

1274. 矩形内船只的数目
二维矩阵

class Solution {
public:
    int longestSubstring(string s, int k) {
        vector<int> hash(26);
        for(auto ch:s){
            hash[ch-'a']++;
        }
        int i=0;
        while(i<s.size()&&hash[s[i]-'a']>=k) i++;
        if(i==s.size()) return s.size();
        //此时字符s[i]出现次数小于k
        int l=longestSubstring(s.substr(0,i),k);//左边的最大长度
        while(i<s.size()&&hash[s[i]-'a']<k) i++;//略过不能使用的值
        int r=longestSubstring(s.substr(i),k); //右边的最大长度
        return max(l,r);
    }
};

根号分治
P3396 哈希冲突

CDQ分治¶

常与树状数组结合用于解决偏序问题
思想

例题¶

P3810 【模板】三维偏序（陌上花开）

分块与莫队算法¶

分块¶

一种较为简单的实现区间/单点修改、查询的方式m次操作\(O(m\sqrt{n})\)
分块操作
块的大小用block表示
块的数目用t表示
用st[i]和ed[i]表示块i第一个和最后一个元素的位置(或者直接使用二维数组)
- st[i]=(i-1)*block+1 ed[i]=i*block
用pos[i]表示第i个元素所属于的块pos[i]=（i-1)/block+1
分\(\lceil\sqrt{n}\rceil\)个块
块的初始化
```c++ int block = sqrt(n); int t = n/block; if(n%block) t++; for(int i=1;i<=t;i++){ st[i]=(i-1)block+1; ed[i]=iblock-1 } //下标从0开始 st[i]=iblock; ed[i]=min((i+1)block-1,n-1);

ed[t]=n;//不完整块 for(int i=1;i<=n;i++){ pos[i]=(i-1)/block+1; } ```
维护区间和
修改：对于包含在区间中的整块，使用标记数组记录整块上的变化，对于不是整块的碎片化区域
查询：对于完全包含的块，直接用sum和add计算，对于不完全包含的部分对单独元素依次加和并加上add
思想：分为整块和碎片分别处理，对块内进行预处理，对于整块转化为点处理，将复杂度降低

void change(int L,int R,int d){
    int p=pos[L],q=pos[R];
    if(p==q){//特殊情况，位于一块
        for(int i=L;i<=R;i++)a[i]+=d;
        sum[p]+=d*(R-L+1);
    }
    else{
        for(int i=p+1;i<=q-1;i++)add[i]+=d;//先整块处理
        for(int i=L;i<=ed[p];i++)a[i]+=d;//对两端进行碎片处理
        sum[p]+=d*(ed[p]-L+1);
        for(int i=st[q];i<=R;i++)a[i]+=d;
        sum[q]+=d*(R-st[q]+1);
    }
}
long long ask(int L,int R){
    int p=pos[L],q=pos[R];
    long long ans=0;
    if(p==q){
        for(int i=L;i<=R;i++)ans+=a[i];
        ans+=add[p]*(R-L+1);
    }
    else{
        for(int i=p+1;i<=q-1;i++)ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
        for(int i=L;i<=ed[p];i++)ans+=a[i];
        ans+=add[p]*(ed[p]-L+1);
        for(int i=st[q];i<=R;i++)ans+=a[i];
        ans+=add[q]*(R-st[q]+1);
    }
    return ans;
}

整除分块¶

用于解决整除求和的问题\(\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\)
复杂度\(O(\sqrt{n})\)
分块，同时处理结果相同的区间
对于每一块有\(E=n/(m/L)\)
```c++ #include using namespace std; int main(){ long long n,L,R,ans=0; cin >> n; for(L=1;L<=n;L=R+1){ R = n/(n/L); //计算R，让分块右移 ans += (R-L+1)*(n/L); //分块求和 } cout << ans; //打印和 }

ll dist_sum(ll n,ll k){ ll L,R,ans=0; for(L=1;L<=min(n,k);L=R+1){ R = min(n,k/(k/L)); ans += (R-L+1)(k/L); } return ans; } //带取模版本 ll dist_sum(ll n,ll k){ ll L,R,ans=0; for(L=1;L<=min(n,k);L=R+1){ R = min(n,k/(k/L)); ans+=((R-L+1)%mod)(k/L%mod); ans%=mod; } return ans; } ```

也可以处理\(\sum_{i=1}^n\lfloor\frac{k}{i}\rfloor\)
P2261 余数求和
P3935 Calculating

例题¶

P2801 教主的魔法
分块+维护块内次序，二分查找：对于整个加减的块，快内顺序不会发生变化，对于碎片处理的需要重新排序（但是这个数据规模可以保证在\(\sqrt n\)）
```c++ #include using namespace std; typedef long long ll;

int main() { int n,q; cin>>n>>q; int block=sqrt(n); int t=n/block; if(n%block!=0) t++; vectorpos(n),st(t),ed(t),add(t); vector>arr(n); for(int i=0;i for(int i=0;i\>type>>l>>r>>x; --l; --r; if(type=='M'){ for(int i=0;i<t;i++){ if(ed[i]r)break; else if(l<=st[i]&&r>=ed[i]){ add[i]+=x; } else{ for(int j=max(l,st[i]);j<=min(r,ed[i]);j++){ arr[pos[j]].first+=x; } sort(arr.begin()+st[i],arr.begin()+ed[i]+1); for(int j=st[i];j<=ed[i];j++){ pos[arr[j].second]=j; } } } } else{ int ans=0; for(int i=0;i<t;i++){ if(ed[i]r)break; else if(l<=st[i]&&r>=ed[i]){ ans+=ed[i]-st[i]+1-(lower_bound(arr.begin()+st[i],arr.begin()+ed[i]+1,make_pair(x-add[i],0))-arr.begin()-st[i]); } else{ for(int j=max(l,st[i]);j<=min(r,ed[i]);j++){ if(arr[pos[j]].first+add[i]>=x) ans++; } } } printf("%d\n",ans); } } return 0; } ```
弹飞绵样
处理从快内每个位置弹出每个块的次数以及落点，修改时也只需要对一个块进行修改

莫队算法¶

离线+暴力+分块，用于解决不修改只查询的问题
在线算法中的非强制在线算法（前面的答案不用做后面的提问）也可以转化为离线进行处理
复杂度通常为\(O(n\sqrt n)\)
例题：查询区间内元素种类数目（初始给出数组，之后进行多次查询）
先考虑暴力法，这里使用双指针，L表示区间左端点，R表示区间右端点，初始时从0开始，L经过的点数字出现次数--，R经过的点++；对m个查询，只需要不断移动区间即可，可以对区间左端点排序（这样L就保持递增），但是右端点不具有单调性，因此R指针会左右往返。时间复杂度为\(O(mn)\)
用(x,y)表示区间，任何一个区间都可以用图上一点表示（由于x<=y都在斜线上方）。计算量就等于点之间的曼哈顿距离，因而想要找到一条最短路径。
莫队算法：先把数组分块，然后把查询的区间按左端点所在块号进行排序，块号相同时按右端点进行排序
左指针每次的移动范围被限定在一个块内，总共的复杂度为\(O(m\sqrt n)\)
右指针在每个块内保持递增，因此总共复杂度为\(O(n\sqrt n)\)
进一步优化：奇数块正排序；偶数块反排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
struct node{           //离线记录查询操作
    int L, R, k;       //k：查询操作的原始顺序
}q[N];
int pos[N];
int ans[N];
int cnt[N];            //cnt[i]: 统计数字i出现了多少次
int a[N];
bool cmp(node a, node b){
//按块排序，就是莫队算法：
    if(pos[a.L] != pos[b.L])              //按L所在的块排序，如果块相等，再按R排序
        return pos[a.L] < pos[b.L];
    if(pos[a.L] & 1)   return a.R > b.R;  //奇偶性优化，如果删除这一句，性能差一点
    return a.R < b.R;     
}
int ANS = 0;
void add(int x){     //扩大区间时（L左移或R右移），增加数x出现的次数
    cnt[a[x]]++;
    if(cnt[a[x]]==1)  ANS++;     //这个元素第1次出现
}
void del(int x){     //缩小区间时（L右移或R左移），减少数x出现的次数
    cnt[a[x]]--;
    if(cnt[a[x]]==0)  ANS--;     //这个元素消失了
}
int main(){ 
    int n; scanf("%d",&n);
    int block = sqrt(n);         //每块的大小
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);       //读第i个元素
        pos[i]=(i-1)/block + 1;  //第i个元素所在的块
    }
    int m; scanf("%d",&m);          
    for(int i=1;i<=m;i++){       //读取所有m个查询，离线处理
        scanf("%d%d",&q[i].L, &q[i].R);
        q[i].k = i;              //记录查询的原始顺序
    }
    sort(q+1, q+1+m, cmp);       //对所有查询排序
int L=1, R=0;                //左右指针的初始值。思考为什么？
    for(int i=1;i<=m;i++){
        while(L<q[i].L)  del(L++);     //{del(L); L++;}  //缩小区间：L右移
        while(R>q[i].R)  del(R--);     //{del(R); R--;}  //缩小区间：R左移
while(L>q[i].L)  add(--L);     //{L--; add(L);}  //扩大区间：L左移
        while(R<q[i].R)  add(++R);     //{R++; add(R);}  //扩大区间：R右移
        ans[q[i].k] = ANS;
    }
    for(int i=1;i<=m;i++)   printf("%d\n",ans[i]);  //按原顺序打印结果
    return 0;
}

带修改的莫队算法¶

莫队算法也能处理比较简单的单点修改，时间复杂度为\(O(mn^{\frac 23})\)
比如查询区间内元素种类数目基础上加上可以单点修改一个点的种类
也是需要进行离线处理，记录查询操作时增加一个值表示查询前进行了多少次修改（L，R，t）
现在点的移动就还需要考虑t（1<=t<=m），当两个查询的t不同时需要暴力修改补上变化
此时的莫队算法就对应一个立体空间(L,R,t)，计算复杂度仍为曼哈顿距离
分块思路：按照左端点进行排序->左端点相同的按照有端点进行排序->右端点相同的按照t进行排序
假设分为B块：对于x计算量为 \(mB\) ，对于y同样为 \(mB\) ，对于t在xy确定的方格内单向移动最大为\(m*(n/B)^2\)
当\(B=n^{\frac23}\)时取得最佳复杂度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
inline void read(T &a)
{
   T s = 0, w = 1;
   char c = getchar();
   while(c < '0' || c > '9')
   {
       if(c == '-') w = -1;
       c = getchar();
   }
   while(c >= '0' && c <= '9')
   {
       s = (s << 1) + (s << 3) + (c ^ 48);
       c = getchar();
   }
   a = s*w;
}
const int N = 1e6+10;
int pos[N],cnt[N],res=0,p_l=0,p_r=-1,p_t=0,ans[N],a[N];
vector<pair<int,int>>modify;
struct node{
    int l,r,t,k;
    node(int l,int r,int t,int k):l(l),r(r),t(t),k(k){}
    node(){}
    bool operator < (const node &a)const{
        if(pos[l]!=pos[a.l]) return pos[l]<pos[a.l];
        if(pos[r]!=pos[a.r]) return pos[r]<pos[a.r];
        return pos[t]<pos[a.t];
    }
}q[N];
//注意l与r的区别，l到x但是不包含x，r到x但是r包含x
void movel(int l){
    while(p_l<l){
        if(cnt[a[p_l]]==1) res--;
        cnt[a[p_l]]--;
        p_l++;
    }
    while(p_l>l){
        p_l--;
        if(cnt[a[p_l]]==0) res++;
        cnt[a[p_l]]++;
    }
}
void mover(int r){
    while(p_r<r){
        p_r++;
        if(cnt[a[p_r]]==0) res++;
        cnt[a[p_r]]++;
    }
    while(p_r>r){
        if(cnt[a[p_r]]==1) res--;
        cnt[a[p_r]]--;
        p_r--;
    }
}
void movet(int t){
    //使用非常巧妙的swap，当前的值就是之后再经过这条修改的目的值（因为t一定是顺序往返修改的）
    while(p_t<t){
        int x=modify[p_t].first;
        //在范围内进行调整
        if(p_l<=x&&x<=p_r){
            if(cnt[a[x]]==1) res--;
            cnt[a[x]]--;
            swap(a[x],modify[p_t].second);
            if(cnt[a[x]]==0) res++;
            cnt[a[x]]++;
        }
        //不在范围内也要对a修改！！！
        else
            swap(a[x],modify[p_t].second);
        p_t++;
    }
    while(p_t>t){
        p_t--;
        int x=modify[p_t].first;
        if(p_l<=x&&x<=p_r){
            if(cnt[a[x]]==1) res--;
            cnt[a[x]]--;
            swap(a[x],modify[p_t].second);
            if(cnt[a[x]]==0) res++;
            cnt[a[x]]++;
        }
        else
            swap(a[x],modify[p_t].second);
    }
}
int main(){
    int n,m,block,cnt=0,mcnt=0;
    read(n);read(m);
    block=pow(n,2.0/3);
    for(int i=0;i<n;i++){
        read(a[i]);
    }
    //预处理分块结果
    for(int i=0;i<N;i++)
        pos[i]=i/block;
    for(int i=0;i<m;i++){
        char c[5];
        scanf("%s",c);
        int x,y;
        read(x);read(y);
        if(c[0]=='Q'){
            q[cnt]=node(x-1,y-1,mcnt,cnt);
            cnt++;
        }
        else{
            //对修改计数
            mcnt++;
            modify.emplace_back(x-1,y);
        }
    }
    //对查询排序
    sort(q,q+cnt);
    for(int i=0;i<cnt;i++){
        int l=q[i].l,r=q[i].r,t=q[i].t;
        //调整坐标
        movel(l);
        mover(r);
        movet(t);
        ans[q[i].k]=res;
    }
    //还原结果
    for(int i=0;i<cnt;i++)
        printf("%d\n",ans[i]);
    return 0;
}

其它类型的莫队算法¶

如果其他数据结构的问题能转化为一维数组上的区间问题，那么就能使用莫队算法
树上莫队
利用欧拉序将整棵树的节点转化为一维数组，路径也就变成了区间问题

例题¶

块状链表¶

块状链表适用于处理数据空间发生变化的情况，如进行插入/删除
块状链表在插入、删除之后要通过合并、分裂进行维护，保证每个块的大小为\(\sqrt n\)
平均单次操作复杂度为\(O(\sqrt n)\)