简介
莫队是一种优美的暴力算法~（——by Daniel_yuan dalao）。
例题
例题出自：
莫队
莫队大全
[数据结构]莫队
（建议按顺序刷题~）
P3901 数列找不同
分析
板子，速速切掉！！！
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
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 << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 1e5 + 10;
int n, q, ans;
int a[N];
int block, b[N];
struct node{
int l, r, id;
bool operator < (const node &x) const{
return (b[l] == b[x.l] ? r < x.r : l < x.l);
}
}que[N];
int cnt[N];
void add(int pos){
if (++cnt[a[pos]] == 1) ans++;
}
void del(int pos){
if (--cnt[a[pos]] == 0) ans--;
}
int L, R;
bool sum[N];
int main(){
n = read(), q = read();
block = sqrt(n);
for (int i = 1; i <= n; i++){
a[i] = read();
b[i] = (i - 1) / block + 1;
}
for (int i = 1; i <= q; i++){
que[i].l = read(), que[i].r = read(), que[i].id = i;
}
sort(que + 1, que + q + 1);
for (int i = 1; i <= q; i++){
int l = que[i].l, r = que[i].r;
while (L < l) del(L++);
while (L > l) add(--L);
while (R > r) del(R--);
while (R < r) add(++R);
if (ans == r - l + 1) sum[que[i].id] = 1;
}
for (int i = 1; i <= q; i++){
printf("%s\n", (sum[i] ? "Yes" : "No"));
}
return 0;
}
FREQUENT - Frequent values
分析
恶心的多测题，板子，但是莫队先扩张再收缩。
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
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 << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 1e5 + 10;
int n, m, k, ans;
int a[N], s[N];
int block, b[N];
struct node{
int l, r, id;
bool operator < (const node &x) const{
return (b[l] == b[x.l] ? r < x.r : l < x.l);
}
}q[N];
int cnt[N], tot[N];
void add(int pos){
tot[cnt[a[pos]]]--;
cnt[a[pos]]++;
tot[cnt[a[pos]]]++;
ans = max(ans, cnt[a[pos]]);
}
void del(int pos){
tot[cnt[a[pos]]]--;
if (tot[cnt[a[pos]]] == 0 && cnt[a[pos]] == ans) ans--;
cnt[a[pos]]--;
tot[cnt[a[pos]]]++;
}
int L = 1, R;
int sum[N];
int main(){
while (n = read()){
if (n == 0) break;
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(q, 0, sizeof q);
memset(s, 0, sizeof s);
memset(cnt, 0, sizeof cnt);
memset(tot, 0, sizeof tot);
memset(sum, 0, sizeof sum);
m = read();
block = sqrt(n);
for (int i = 1; i <= n; i++){
s[i] = a[i] = read();
b[i] = (i - 1) / block + 1;
}
sort(s + 1, s + n + 1);
int len = unique(s + 1, s + n + 1) - s - 1;
for (int i = 1; i <= n; i++){
a[i] = lower_bound(s + 1, s + len + 1, a[i]) - s;
}
for (int i = 1; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].id = i;
}
sort(q + 1, q + m + 1);
L = 1, R = 0, ans = 0;
for (int i = 1; i <= m; i++){
int l = q[i].l, r = q[i].r;
while (L > l) add(--L);
while (R < r) add(++R);
while (L < l) del(L++);
while (R > r) del(R--);
sum[q[i].id] = ans;
}
for (int i = 1; i <= m; i++){
printf("%d\n", sum[i]);
}
}
return 0;
}
P1972 [SDOI2009] HH的项链
分析
前言：莫队不可过。
莫队板子，拿到 \(40+\) 分就ok了。
代码
本人写的是正解树状数组做法。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,q,g[1145141],a[1145141],k[1145141],l,r,cq,as[1145141];
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 << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
struct ask{
int l,r,num;
}qu[1145141];
bool cmp(ask a,ask b){
return k[a.l]==k[b.l]?(k[a.l]%2==1?a.r<b.r:a.r>b.r):a.l<b.l;
}
void add(int k){
g[a[k]]++;
if(g[a[k]]==1) cq++;
}
void del(int k){
g[a[k]]--;
if(g[a[k]]==0) cq--;
}
int main(){
n=read();
for (register int i=1;i<=n;i++) a[i]=read();
q=read();
int sq=n*2/sqrt(n);
for(register int i=1;i<=n;i++) k[i]=(i-1)/sq;
for(register int i=1;i<=q;i++)
qu[i].l=read(),qu[i].r=read(),qu[i].num=i;
sort(qu+1,qu+q+1,cmp);
for(register int i=1;i<=q;i++){
while(l>qu[i].l){
g[a[--l]]++;
cq+=(g[a[l]]==1);
}
while(l<qu[i].l){
g[a[l]]--;
cq-=(g[a[l]]==0);
++l;
}
while(r<qu[i].r){
g[a[++r]]++;
cq+=(g[a[r]]==1);
}
while(r>qu[i].r){
g[a[r]]--;
cq-=(g[a[r]]==0);
--r;
}
as[qu[i].num]=cq;
}
for(register int i=1;i<=q;i++){
write(as[i]);
printf("\n");
}
}
P1494 [国家集训队] 小 Z 的袜子
分析
第一眼看上去，哇塞，莫队题，直接切掉。但是看到概率，直接就退缩了。其实只需要用可能次数除以总次数就ok了。
假如有 \(n\) 条相同颜色的袜子，则有 \(n + (n - 1) + (n - 2) + (n - 3) + \dots + 1\)，然后我们可以发现这样就可以跑莫对了，总方案数就是
$$\tbinom{r - l + 1}{2}$$
然后约个分就写完了。（是不是很简单）
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
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 << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 5e4 + 10;
int n, m, ans;
int a[N];
int block, b[N];
struct node{
int l, r, id;
bool operator < (const node &x) const{
return (b[l] == b[x.l] ? r < x.r : l < x.l);
}
}q[N];
int cnt[N];
void add(int pos){
ans += cnt[a[pos]];
cnt[a[pos]]++;
}
void del(int pos){
cnt[a[pos]]--;
ans -= cnt[a[pos]];
}
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
void get_gcd(int &a, int &b){
int g = gcd(a, b);
a /= g, b /= g;
}
int L = 1, R;
int sum1[N], sum2[N];
signed main(){
n = read(), m = read();
block = sqrt(n);
for (int i = 1; i <= n; i++){
a[i] = read();
b[i] = (i - 1) / block + 1;
}
for (int i = 1; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].id = i;
}
sort(q + 1, q + m + 1);
for (int i = 1; i <= m; i++){
int l = q[i].l, r = q[i].r;
if (l == r){
sum1[q[i].id] = 0, sum2[q[i].id] = 1;
continue;
}
while (L < l) del(L++);
while (L > l) add(--L);
while (R > r) del(R--);
while (R < r) add(++R);
sum1[q[i].id] = ans;
sum2[q[i].id] = (r - l + 1) * (r - l) / 2;
get_gcd(sum1[q[i].id], sum2[q[i].id]);
}
for (int i = 1; i <= m; i++){
printf("%d/%d\n", sum1[i], sum2[i]);
}
return 0;
}
P2709 小B的询问
分析
第一眼想到莫队，然后觉得需要前缀和优化。但真的有必要开个数组进行前缀和优化吗，其实直接用桶记录每个数出现次数，再按照题目的意思相加就行了。
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
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 << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 1e5 + 10;
int n, m, k, ans;
int a[N];
int block, b[N];
struct node{
int l, r, id;
bool operator < (const node &x) const{
return (b[l] == b[x.l] ? r < x.r : l < x.l);
}
}q[N];
int cnt[N];
void add(int pos){
ans -= cnt[a[pos]] * cnt[a[pos]];
cnt[a[pos]]++;
ans += cnt[a[pos]] * cnt[a[pos]];
}
void del(int pos){
ans -= cnt[a[pos]] * cnt[a[pos]];
cnt[a[pos]]--;
ans += cnt[a[pos]] * cnt[a[pos]];
}
int L = 1, R;
int sum[N];
int main(){
n = read(), m = read(), k = read();
block = sqrt(n);
for (int i = 1; i <= n; i++){
a[i] = read();
b[i] = (i - 1) / block + 1;
}
for (int i = 1; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].id = i;
}
sort(q + 1, q + m + 1);
for (int i = 1; i <= m; i++){
int l = q[i].l, r = q[i].r;
while (L < l) del(L++);
while (L > l) add(--L);
while (R > r) del(R--);
while (R < r) add(++R);
sum[q[i].id] = ans;
}
for (int i = 1; i <= m; i++){
printf("%d\n", sum[i]);
}
return 0;
}