众所周知，欣隆妹妹是个毒瘤。
经常出毒瘤数据结构题。
出得挺多的是莫队。
所以今天我们来聊聊莫队
可爱的由乃。
part one - 什么是莫队？
。。。
part two - 莫队的原理与实现:
第一步，让询问离线。
你将每一个询问放进一个结构体，然后对询问进行分块，每一个询问对应的块记为bel，目前，块大小最优为n/sqrt(m*2/3)
如何排序让时间复杂度正确？？？主流的做法是，第一关键字为左端点所在的块，如果同块则比右端点
你还可以尝试如果左端点所在块为奇数则a.r>b.r否则a.r<b.r,这样可能比较块，但也挺玄学
莫队需要两个指针，每次移动两个指针，让他对应到当前的l,r，每一次删除或加入时更新答案
part three 莫队基础题:
1.小z的袜子：
求区间内取到相同颜色袜子的概率（差不多就是方案数
设每一种颜色在区间中出现的次数为c[i],那么对答案的贡献就是c[i]*(c[i]-1)/2
然后每一次删除，插入，更改c[i],重新算一遍贡献，然后减去对但减去原来的贡献加上新的贡献
code::(贡献一波手码的排序）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define Temp template<typename T>
Temp inline void read(T &x) {
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=w;
}
const int maxn=5e5+10;
int a[maxn],t[maxn],f[maxn],res[maxn],x[maxn],y[maxn],bh[maxn];
int n,m,left=1,right=1,p;
long long ans=0;
inline int gcd(int n,int m) {
if(n%m==0) return m;
return gcd(m,n%m);
}
inline void write(long long x) {
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline void qsort(int l,int r) {
int i=l,j=r,mid=(l+r)>>1,tl=x[(l+r)>>1],tr=y[(l+r)>>1];
do{
if((i/p)==(j/p)) {
while(x[i]<tl) ++i;
while(tl<x[j]) --j;
if(i<=j) {
std::swap(x[i],x[j]);
std::swap(y[i],y[j]);
std::swap(bh[i],bh[j]);
++i;
--j;
}
}
else {
while(y[i]<tr) ++i;
while(tr<y[j]) --j;
if(i<=j) {
std::swap(x[i],x[j]);
std::swap(y[i],y[j]);
std::swap(bh[i],bh[j]);
++i;
--j;
}
}
}while(i<=j);
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main() {
read(n);read(m);
p=sqrt(n);
for (Rint i=1;i<=n;++i) {
read(a[i]);
}
for (Rint i=1;i<=m;++i) {
read(x[i]);read(y[i]);bh[i]=i;
}
qsort(1,m);
t[a[1]]++;
for (Rint i=1;i<=m;++i) {
int ll=x[i];
int rr=y[i];
while(left>ll) {
--left;
ans+=t[a[left]];
t[a[left]]++;
}
while(right<rr) {
++right;
ans+=t[a[right]];
t[a[right]]++;
}
while(left<ll) {
t[a[left]]--;
ans-=t[a[left]];
++left;
}
while(right>rr) {
t[a[right]]--;
ans-=t[a[right]];
--right;
}
f[bh[i]]=ans;
res[bh[i]]=right-left+1;
}
for (Rint i=1;i<=m;++i) {
if(f[i]==0) {
putchar('0');putchar('/');putchar('1');putchar('\n');
}
else {
long long tot=res[i];
long long c=gcd(f[i],tot*(tot-1)>>1);
write(f[i]/c);putchar('/');write(tot*(tot-1)/c/2);putchar('\n');
}
}
return 0;
}
2.HH的项链
莫队，统计出现次数。
每一次插入，当前a[i]的出现次数+1,如果a[i]的出现次数为1，答案+1
每一次删除，当前a[i]的出现次数-1,如果a[i]的出现次数为0，答案-1
题太菜就没code了
3.采花
莫队，还是统计出现次数
每一次插入，当前a[i]的出现次数+1,如果a[i]的出现次数为2，答案+1
每一次删除，当前a[i]的出现次数-1,如果a[i]的出现次数为1，答案-1
code::(为啥要给的来着
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct query{
int l,r,id;
}q[300005];
int num[300005],Ans[300005],n,m,a[300005],bel[300005],sz,ans=0,c;
int read() {
register int x=0,w=1;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*w;
}
bool cmp(query a,query b) {
if(bel[a.l]!=bel[b.l]) return a.l<b.l;
else if(bel[a.l]&1) return a.r>b.r;
else return a.r<b.r;
}
void ins(int x) {
++num[a[x]];
if(num[a[x]]==2) ++ans;
}
void del(int x) {
--num[a[x]];
if(num[a[x]]==1) --ans;
}
int main() {
n=read();c=read();m=read();
sz=m/sqrt(n*2/3);
for (int i=1;i<=n;++i) a[i]=read();
for (int i=1;i<=n;++i) bel[i]=(i-1)/sz+1;
for (int i=1;i<=m;++i){
q[i].l=read();q[i].r=read();q[i].id=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++);
while(l>q[i].l) ins(--l);
while(r<q[i].r) ins(++r);
while(r>q[i].r) del(r--);
Ans[q[i].id]=ans;
}
for (int i=1;i<=m;++i) printf("%d\n",Ans[i]);
return 0;
}part five:Ynoi
1.这是我自己的发明
换根，就是分类讨论以下，其实就是dfs序上的两个区间
所以就成了不换根
如果颜色出现次数>sqrt(n)暴力
否则，就是类似二维数点。
因为修改O(m)个，查询O(nsqrt(n))个，考虑用分块代替树状数组，这样可以根号平衡
2.跳进兔子洞
莫队+bitset
3.此时此刻的光辉
因为质数个数少，所以根号分治
前<sqrt(n)的质数暴力，后面的莫队维护
所以时间复杂度是对的
end.
计划补充的内容：
1.回滚莫队
2.二次离线莫队
orz nzhtl1477