莫队
参考博客
玄学暴力区间操作算法
PPT解释的很清楚啦~, 导致我没什么可写的 \(qwq\)
把所有询问离线下来后排序（左端点按块，右端点升序），然后从一个小区间通过左右端点的移动扩大区间，更新答案。
复杂度主要在区间扩展,也就是左右指针的移动，对于莫队所有的优化几乎都是调整分块或排序减少指针移动次数。
本质就是暴力，但是复杂度太玄学了，完美剪枝。
排序巧妙优化复杂度，带来NOIP前的最后一丝宁静。几个活蹦乱跳的指针的跳跃次数，决定着莫队算法的优劣……
1.奇偶化排序
对于每一个块来说，询问的右端点都是从小到大排序，
每次遍历完一个块右指针指在最右端，然后又千里迢迢跑回最左端，中间完全没干活。
也就是右指针只有从左到右移动是有效的，从右到左的移动完全没用。
所以加大右端点工作效率，右端点对于奇数块升序排序，对于偶数块降序排序。
这样右端点就24小时全程加班，大大减少移动次数。
最佳分块大小： \(\frac{n}{\sqrt{m}}\)
（例题： HH的项链）
#include<bits/stdc++.h>
using namespace std;
const int N = 50005, M = 200005;
int n,m,a[N],l=1,r=0,cnt[1000005],tmp;
struct Q
{int l,r,id;
} q[M];
int ans[M];
int L[10000],R[10000],bl[N];
void bui()//分块
{int cnt=n/sqrt(m);for(int i=1;i<=cnt;i++){L[i]=n/cnt*(i-1)+1;R[i]=n/cnt*i;}R[cnt]=n;for(int i=1;i<=cnt;i++)for(int j=L[i];j<=R[i];j++)bl[j]=i;
}
bool cmp(Q &x,Q &y)
{if(bl[x.l]!=bl[y.l]) return bl[x.l]<bl[y.l];if(bl[x.l] & 1) return x.r<y.r;//奇偶化return x.r>y.r;
}
void add(int x)
{if(!cnt[x]) tmp++;cnt[x]++;
}
void del(int x)
{cnt[x]--;if(!cnt[x]) tmp--;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);bui();//注意调用for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);q[i]={x,y,i};}sort(q+1,q+1+m,cmp);for(int i=1;i<=m;i++){int x=q[i].l,y=q[i].r;while(l>x) add(a[--l]);while(l<x) del(a[l++]);while(r>y) del(a[r--]);while(r<y) add(a[++r]);ans[q[i].id]=tmp;}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}
带修莫队
众所周知，莫队是一种离线算法，不支持修改。
但是莫队这种 暴力+优化 的思想仍可以应用。
我们从最简单的思路想，如果把修改也离线下来呢？
那也就是在 \(l,r\) 轴以外再加一维 \(t\) 轴，维护当前的修改数。
这就是带修莫队，把二维的区间变成三维。
那么怎么实现时间轴的移动呢？
首先我们要记录每一次查询是在哪一次修改后，
然后判断本次修改对当前区间的影响：
-
修改位置在当前区间外，没有影响。
-
修改位置在当前区间内，那也就是删去一个修改位置的值，添加一个修改后的值。
最后记得把原数组也修改。
这里有一个很巧妙的操作，对于原数组，需要支持两种操作（改过去和改回来），
我们可以把修改值和原值交换，那么两种操作其实就合并成一种了。
至于排序时，左右端点都按分块排，相同比时间轴。
最佳分块大小： \(n^{\frac{2}{3}}\) ( \(cnt=n^{\frac{1}{3}}\))
(例题：数颜色)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6,M = 133335;
int n,m,a[M],cnt[N],mq,mre,tmp,l=1,r=0,t=0,ans[M];
struct Q
{int l,r,t,id;
} q[M];
struct R
{int x,c;
} re[M];
int L[3005],R[3005],bl[M];
void bui()
{int cnt=pow(n,1.0/3);for(int i=1;i<=cnt;i++){L[i]=n/cnt*(i-1)+1;R[i]=n/cnt*i;}R[cnt]=n;for(int i=1;i<=cnt;i++)for(int j=L[i];j<=R[i];j++)bl[j]=i;
}
bool cmp(Q &x,Q &y)
{if(x.l!=y.l) return bl[x.l]<bl[y.l];if(x.r!=y.r) return bl[x.r]<bl[y.r];return x.t<y.t;
}
void add(int x)
{if(!cnt[x]) tmp++;cnt[x]++;
}
void del(int x)
{cnt[x]--;if(!cnt[x]) tmp--;
}
void mdf(int x)
{if(re[x].x>=l&&re[x].x<=r){del(a[re[x].x]);add(re[x].c);}swap(a[re[x].x],re[x].c);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++){int x,y;char c;scanf(" %c%d%d",&c,&x,&y);if(c=='Q') q[++mq]={x,y,mre,mq};else re[++mre]={x,y};}bui();sort(q+1,q+1+mq,cmp);for(int i=1;i<=mq;i++){int x=q[i].l,y=q[i].r,now=q[i].t;while(l>x) add(a[--l]);while(l<x) del(a[l++]);while(r<y) add(a[++r]);while(r>y) del(a[r--]);while(t>now) mdf(t--);while(t<now) mdf(++t);ans[q[i].id]=tmp;}for(int i=1;i<=mq;i++) printf("%d\n",ans[i]);return 0;
}
回滚莫队
回滚莫队用于处理一些只能进行 \(add\) 或 \(del\) 其中一种操作的。
我们将每一个块的左端点或右端点设为基点，保留这个状态，然后每次 "滚回来"。
之前写过博客 回滚莫队
最佳分块大小： \(\sqrt{n}\) (???)
（例题：历史研究）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;
int n,m;
int a[N],cnt[N],cntb[N],f[N],tot;
LL tmp,ans[N];
int l,r;
map<int,int> mp;
struct Q
{int l,r,id;
} q[N];
int L[4000],R[4000],bl[N];
void bui()
{int cnt = sqrt(n);for(int i=1;i<=cnt;i++){L[i]=n/cnt*(i-1)+1;R[i]=n/cnt*i;}R[cnt]=n;for(int i=1;i<=cnt;i++){for(int j=L[i];j<=R[i];j++){bl[j]=i;}}
}
void add(int x)
{cnt[x]++;tmp=max((LL)cnt[x]*f[x],tmp);
}
bool operator < (Q &x,Q &y)
{if(bl[x.l]!=bl[y.l]) return bl[x.l]<bl[y.l];else return x.r<y.r;
}
void mo_q()
{for(int i=1;i<=m;){memset(cnt,0,sizeof(cnt)); tmp=0;int j=i; int right=bl[q[i].l];while(right==bl[q[j].l]&&j<=m) j++;//找到左端点在同一块内的r=R[right]; l=r+1;while(i<j){ if(q[i].r<=R[right])//同一块内{for(int k=q[i].l;k<=q[i].r;k++) add(a[k]);ans[q[i].id]=tmp;tmp=0; memset(cnt,0,sizeof(cnt));i++;}else//不同块{while(r<q[i].r) add(a[++r]);memcpy(cntb,cnt,sizeof(cnt));LL bbb=tmp;while(l>q[i].l) add(a[--l]);ans[q[i].id]=tmp; i++;tmp=bbb;l=R[right]+1;memcpy(cnt,cntb,sizeof(cntb));}}}
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(mp[a[i]]==0){mp[a[i]]=++tot; f[tot]=a[i];a[i]=tot;}else a[i]=mp[a[i]];}bui();//注意调用for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);q[i]=Q{x,y,i};}sort(q+1,q+1+m);mo_q();//注意调用for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}
完结撒花 ✿ヽ(°▽°)ノ✿
好像还有个树上莫队，遇到再写吧。
\(\mathbb{mo\_q}\)
