前置芝士
分块
算法理解
一种暴力顺序的优化
离线+暴力+分块
通常用于不带修只查询的一类问题
模板题P1972 [SDOI2009] HH的项链
首先使用暴力法求解此题
我们设我们有一个 \(L,R\) 表示现在扫到 \([L,R]\) 区间，对于一个询问 \((l,r)\) 我们暴力的将 \(L->l\)，\(R->r\) 然后一格一格的移动，通过维护一个 \(cnt[a[i]]\) 表示 \(a[i]\) 出现的次数来统计答案，这样做因为每次 \(L,R\) 的移动是 \(O(n)\) 的所以总复杂度 \(O(nm)\)
莫队优化：将时间复杂度控制在 \(O(n\sqrt n+m\sqrt n)\)
我们会发现影响时间复杂度的是什么呢？ \(L,R\) 的震荡幅度
我们将询问 \((l,r)\) 看成平面上的一个点对
每一次移动的时间复杂度就是相邻两个点的曼哈顿距离，可以发现当我们对于 \(l\)，排序后 \(r\) 的振幅达到了 \(O(n)\)
所以我们可不可以限制一下振幅在一个区间内来控制复杂度
想到了分块，我们按照左端点所在块的编号为第一关键字，以右端点为第二关键字排序
考虑一下，左端点的振幅每次被限制在了 \(O(\sqrt n)\) 之内，共有 \(m\) 次操作，左端点移动复杂度为 \(O(m\sqrt n)\)
右端点当左端点在一个块内的顺序时是递增顺序的，也就是说在一个块内右端点移动的复杂度是 \(O(n)\) 的，然后有 \(O(\sqrt n)\) 个块，所以复杂度为 \(O(n\sqrt n)\)
记住右端点不是按块来排序的，因为这样就是一个方格图，无法保证在一个方格中的点的顺序，导致路径增长
还有就是块长不一定是 \(O(\sqrt n)\) 这是根据块长和块的个数带进具体题目中算出来的最优解法，具体题目具体分析
莫队优化：
莫队常数很小，但同时一些卡莫队的题需要卡卡常才能过
有一种优化是奇偶性排序，在块的编号为奇数时我们按照右端点升序排序，偶数时降序，可以优化一点复杂度
总结：莫队就是在暴力的基础上离线优化了一下暴力的枚举顺序，使其控制在 \(O((n+m)\sqrt n)\) 的复杂度内
代码也非常好写：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,t,block,ans;
int a[N],pos[N],cnt[N],num[N];
struct query{
int l,r,i;
}ask[N];
void allocate(){
block=(int)sqrt(n);
t=n/block;
if(n%block) t++;
for(int i=1;i<=n;i++){
pos[i]=(i-1)/block+1;
}
}
bool cmp(query x,query y){
if(pos[x.l]==pos[y.l]){
if(pos[x.l]&1) return x.r<y.r;
else return x.r>y.r;
}
return pos[x.l]<pos[y.l];
}
void add(int x){
if(!cnt[a[x]]) ans++;
cnt[a[x]]++;
}
void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]]) ans--;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
allocate();
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
ask[i]={l,r,i};
}
sort(ask+1,ask+1+m,cmp);
int L=1,R=0;
for(int i=1;i<=m;i++){
int l=ask[i].l,r=ask[i].r;
while(L<l) del(L),L++;
while(l<L) L--,add(L);
while(R<r) R++,add(R);
while(r<R) del(R),R--;
num[ask[i].i]=ans;
}
for(int i=1;i<=m;i++){
printf("%d\n",num[i]);
}
}
ps:此题卡莫队，我没有卡过去
P1903 [国家集训队] 数颜色 / 维护队列
带修莫队
莫队本来不支持修改，但通过加一个维度的方式可以使其支持简单修改，我们设 \(t\) 表示在这次查询前经历了 \(t\) 次修改，于是我们就可以维护一次询问 \((l,r,t)\)
然后以l所在的块为第一关键字，r所在的块为第二关键字，t为第三关键字排序
然后我们设块长为 \(B\)，有 \(n/B\) 个块，所以 \(t\) 的在一个被 l,r 限制的方格内单向移动复杂度为 \(O(m)\) 有 \(n^2/B^2\) 个方格，复杂度为 \(O(mn^2/B^2)\)
总复杂度为 \(O(mB+mB+mn^2/B^2)\)，通过计算当 \(B=n^{ \frac{2}{3}}\) 时最优
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=133340,M=1e6+5;
int n,m,tot,block,ans,gg;
int a[N],pos[N],cnt[M],num[N];
struct query{
int l,r;
}ch[N];
struct opera{
int l,r,t,i;
}ask[N];
void allocate(){
block=pow(n,0.666);
for(int i=1;i<=n;i++){
pos[i]=(i-1)/block+1;
}
}
bool cmp(opera x,opera y){
if(pos[x.l]==pos[y.l]){
if(pos[x.r]==pos[y.r]) return x.t<y.t;
return pos[x.r]<pos[y.r];
}
return pos[x.l]<pos[y.l];
}
void add(int x){
if(!cnt[a[x]]) ans++;
cnt[a[x]]++;
}
void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]]) ans--;
}
void change(int l,int r,int t){
if(ch[t].l<=r&&l<=ch[t].l){
del(ch[t].l);
}
swap(a[ch[t].l],ch[t].r);
if(ch[t].l<=r&&l<=ch[t].l){
add(ch[t].l);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
allocate();
for(int i=1;i<=m;i++){
int l,r;
char s[1];
scanf("%s%d%d",s,&l,&r);
if(s[0]=='Q'){
tot++;
ask[tot]={l,r,gg,tot};
}
else{
gg++;
ch[gg]={l,r};
}
}
sort(ask+1,ask+1+tot,cmp);
int L=1,R=0,T=0;
for(int i=1;i<=tot;i++){
int l=ask[i].l,r=ask[i].r,t=ask[i].t;
while(L<l) del(L),L++;
while(l<L) L--,add(L);
while(R<r) R++,add(R);
while(r<R) del(R),R--;
while(T<t) T++,change(L,R,T);
while(t<T) change(L,R,T),T--;
num[ask[i].i]=ans;
}
for(int i=1;i<=tot;i++){
printf("%d\n",num[i]);
}
}