普通莫队
适用范围：离线，区间问询，从 (x) 算出 (x+1,x-1) 的时间复杂度小，以及一切可以用莫队的题目
不适用范围：在线，奇怪的无法增量式求解的问题，以及一切不可以用莫队的题目
由于本人过菜，只学不带修不回滚不二次离线的简单莫队。
假设询问的区间为 ((l,r))，目标函数为 (f(l,r))，那么可以这样做。
- 对 (l,r) 进行莫队玄学排序
- 增量式求解（四个
while）
1 玄学排序
将序列分块。设第 (i) 个数所在块为 (b_i)。
将 ((l,r)) 按照 (b_l) 为第一关键字，(r) 为第二关键字排序。
于是我们得到了一个比较规则
bool cmp(const query &x,const query &y) {
return b[x.l]==b[y.l] ? x.r<y.r : b[x.l]<b[y.l];
}
于是我们按照这个比较规则把所有问询区间排序即可。
2 增量式求解
接下来就是喜闻乐见的四个 while，用来增量式求解。但是需要注意的是 x++ 和 ++x 等烦人的细节。
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(r>q[i].r) del(r--);
设 del 和 add 的复杂度为 (t)，则莫队的复杂度为 (O(ntsqrt n ))
例题
SP3267 D-query
给定序列 (a_{1...n})，(q) 组询问，每组询问为 ([l,r]) 的不同数字的数量。
莫队板子题。del 和 add 函数中只需要对各个数字出现次数进行修改即可。
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=200009;
int n,Q,a[N],bs,b[N],ans[N];
struct query{int l,r,id;}q[N];
bool cmp(const query &x, const query &y) {
return b[x.l]==b[y.l] ? x.r<y.r : b[x.l]<b[y.l];
}
int l=1,r,cnt[1000009],anss;
void inc(int x) {cnt[a[x]]++, anss+=(cnt[a[x]]==1);}
void dec(int x) {cnt[a[x]]--, anss-=(cnt[a[x]]==0);}
void Mo() {
sort(q+1,q+Q+1,cmp);
rep(i,1,Q) {
while(l<q[i].l) dec(l++);
while(l>q[i].l) inc(--l);
while(r<q[i].r) inc(++r);
while(r>q[i].r) dec(r--);
ans[q[i].id]=anss;
}
}
inline int read(){
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int main() {
n=read(); bs=sqrt(n);
rep(i,1,n) a[i]=read(), b[i]=(i-1)/bs+1;
Q=read();
rep(i,1,Q) q[i].l=read(), q[i].r=read(), q[i].id=i;
Mo();
rep(i,1,Q) printf("%d
",ans[i]);
return 0;
}
LG2709 小 B 的询问
还是一道标准的莫队题。
(c_i^2) 可以增量式更新，因为 ((c_i+1)^2-c_i^2=2c_i+1)。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=5e4+9;
int n,m,k,bs,a[N],b[N],ans[N];
struct query {int l,r,id;}q[N];
bool cmp(const query &x,const query &y) {
return b[x.l]==b[y.l] ? x.r<y.r : b[x.l]<b[y.l];
}
int l=1,r,anss,cnt[N];
void inc(int x) {anss+=2*cnt[a[x]]+1, cnt[a[x]]++;}
void dec(int x) {cnt[a[x]]--, anss-=2*cnt[a[x]]+1;}
void Mo() {
sort(q+1,q+m+1,cmp);
rep(i,1,m) {
while(l<q[i].l) dec(l++);
while(l>q[i].l) inc(--l);
while(r<q[i].r) inc(++r);
while(r>q[i].r) dec(r--);
ans[q[i].id]=anss;
}
}
inline int read(){
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
signed main() {
n=read(), m=read(), k=read(), bs=sqrt(n);
rep(i,1,n) a[i]=read(), b[i]=(i-1)/bs+1;
rep(i,1,m) q[i].l=read(), q[i].r=read(), q[i].id=i;
Mo();
rep(i,1,m) printf("%lld
",ans[i]);
return 0;
}
LG1494 小 Z 的袜子
简化一下目标函数 (f(l,r))
[f(l,r)=frac{sum_{i=1}^{n} cnt_i(cnt_i-1) }{(r-l+1)(r-l)}
]
[=frac{-(r-l+1)+sum_{i=1}^{n} cnt_i^2 }{(r-l+1)(r-l)}
]
显然分母可以直接求，分子即上题的形式。需要特殊处理一下 (l=r) 的情况。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=5e4+9;
int n,m,bs,a[N],b[N];
pair<int,int> ans[N];
int gcd(int a,int b) {
if(b==0) return a;
else return gcd(b,a%b);
}
struct query {int l,r,id;}q[N];
bool cmp(const query &x,const query &y) {
return b[x.l]==b[y.l] ? x.r<y.r : b[x.l]<b[y.l];
}
int l=1,r,anss,cnt[N];
void inc(int x) {anss+=2*cnt[a[x]]+1, cnt[a[x]]++;}
void dec(int x) {cnt[a[x]]--, anss-=2*cnt[a[x]]+1;}
void Mo() {
sort(q+1,q+m+1,cmp);
rep(i,1,m) {
if(q[i].l==q[i].r) {ans[q[i].id]=make_pair(0,1); continue;}
while(l<q[i].l) dec(l++);
while(l>q[i].l) inc(--l);
while(r<q[i].r) inc(++r);
while(r>q[i].r) dec(r--);
int g=gcd(anss-r+l-1,(r-l+1)*(r-l));
ans[q[i].id]=make_pair((anss-r+l-1)/g,(r-l+1)*(r-l)/g);
}
}
inline int read(){
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
signed main() {
n=read(), m=read(); bs=sqrt(n);
rep(i,1,n) a[i]=read(), b[i]=(i-1)/bs+1;
rep(i,1,m) q[i].l=read(), q[i].r=read(), q[i].id=i;
Mo();
rep(i,1,m) printf("%lld/%lld
",ans[i].first,ans[i].second);
return 0;
}
LG4137 Rmq Problem / mex
暴力更新。复杂度是错的，但是可以艹过很多点，最后还是被最后一个点卡掉了/kk。
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=2e5+9;
int n,m,bs,a[N],b[N],ans[N];
struct query {int l,r,id;}q[N];
bool cmp(const query &x,const query &y) {
return b[x.l]==b[y.l] ? x.r<y.r : b[x.l]<b[y.l];
}
int l=1,r,cnt[N],mex;
inline void dec(int x) {if(a[x]>n+1) return; cnt[a[x]]--, mex=(!cnt[a[x]]&&a[x]<mex ? a[x] : mex);}
inline void inc(int x) {if(a[x]>n+1) return; cnt[a[x]]++; if(a[x]==mex) while(cnt[mex]) mex++;}
void Mo() {
sort(q+1,q+m+1,cmp);
rep(i,1,m) {
while(l<q[i].l) dec(l++);
while(l>q[i].l) inc(--l);
while(r<q[i].r) inc(++r);
while(r>q[i].r) dec(r--);
ans[q[i].id]=mex;
}
}
inline int read(){
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int main() {
n=read(), m=read(), bs=pow(n+2,1./2);
rep(i,1,n) a[i]=read(), b[i]=(i-1)/bs+1;
rep(i,1,m) q[i].l=read(), q[i].r=read(), q[i].id=i;
Mo();
rep(i,1,m) printf("%d
",ans[i]);
return 0;
}
LG4688 [Ynoi2016]掉进兔子洞
题目求三个区间不同时出现的数的个数。考虑补集转换。所以目标函数被转换为 (r_1+r_2+r_3-l_1-l_2-l_3+3-3 imes) 三个区间公共的数的个数。
求交集？用 bitset！对于每一组询问都维护一个 bitset。当然我们不可能每一个询问都暴力加入数。离线区间可增量问询？用莫队！于是我们用莫队来求出每组询问的一个 bitset 即可。
但是有一个小问题，就是没法开 (10^5) 个 bitset。所以有一个技巧，就是循环利用。什么意思呢？就是我们不是只用一次莫队把所有询问撸完，而是分多次，做多次莫队，这样空间就可以开小一点。
还有一点需要注意。由于 bitset 不能访问负的下标，所以必须先加后减。
本题卡常。有一个莫队卡常小技巧。排序时，cmp 函数可以这么写，常数就会减少很多。然后就卡到了第二面。
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+9, M=25009, P=2500;
inline int read(){
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int n, m, bss, a[N], b[N], ans[M];
int tb[N];
void discrete() {
rep(i,1,n) tb[i]=a[i];
sort(tb+1,tb+n+1);
rep(i,1,n) a[i]=lower_bound(tb+1,tb+n+1,a[i])-tb;
}
struct query {int l, r, id;} q[M*3];
bool cmp(const query &x, const query &y) {
return b[x.l]==b[y.l] ? ((b[x.l]&1) ? x.r<y.r : x.r>y.r) : b[x.l]<b[y.l];
}
bitset<N> anss, bs[M];
int l=1, r, cnt[N];
bool vst[M];
inline void inc(int x) {anss[a[x]+(cnt[a[x]]++)]=1;}
inline void dec(int x) {anss[a[x]+(--cnt[a[x]])]=0;}
inline void init() {
memset(cnt,0,sizeof(cnt));
anss.reset();
l=1, r=0;
}
void work(int m) {
init();
rep(i,1,m) {
q[i*3-2].l=read(), q[i*3-2].r=read(), q[i*3-2].id=i;
ans[i]+=q[i*3-2].r-q[i*3-2].l+1;
q[i*3-1].l=read(), q[i*3-1].r=read(), q[i*3-1].id=i;
ans[i]+=q[i*3-1].r-q[i*3-1].l+1;
q[i*3].l=read(), q[i*3].r=read(), q[i*3].id=i;
ans[i]+=q[i*3].r-q[i*3].l+1;
}
sort(q+1,q+m*3+1,cmp);
rep(i,1,m*3) {
while(l>q[i].l) inc(--l);
while(r<q[i].r) inc(++r);
while(l<q[i].l) dec(l++);
while(r>q[i].r) dec(r--);
bs[q[i].id]=(vst[q[i].id] ? bs[q[i].id]&anss : anss);
vst[q[i].id]=1;
}
rep(i,1,m) printf("%d
",ans[i]-bs[i].count()*3), ans[i]=0, vst[i]=0;
}
int main() {
n=read(), m=read(), bss=pow(n,0.5);
rep(i,1,n) a[i]=read(), b[i]=(i-1)/bss+1;
discrete();
rep(i,1,m) if(i%P==0||i==m) work(i%P ? m%P : P);
return 0;
}