P1494 [国家集训队] 小 Z 的袜子
莫队模板
点击查看代码
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 50005;
typedef long long LL;
int n, m, len, w[N], cnt[N]; // cnt维护出现个数
struct Query { int id, l, r; } queries[N];
LL ans1[N], ans2[N];
int get(int x) { return (x - 1) / len + 1; }
void upd(int x, LL &res, int dif) { // res为每个数出现次数平方和
res -= (LL)cnt[x] * cnt[x], cnt[x] += dif, res += (LL)cnt[x] * cnt[x];
}
int main() {
scanf("%d%d", &n, &m), len = sqrt(n);
for(int i = 1; i <= n; i ++) scanf("%d", w + i);
for(int i = 0; i < m; i ++) scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
std::sort(queries, queries + m, [&](const Query &x, const Query &y) {
if(get(x.l) != get(y.l)) return get(x.l) < get(y.l);
return x.r < y.r;
});
LL res = 0, d;
for(int k = 0, i = 0, j = 1; k < m; k ++) {
auto [id, l, r] = queries[k];
if(l == r) {
ans2[id] = 1;
continue;
}
while(i < r) upd(w[++ i], res, 1);
while(i > r) upd(w[i --], res, -1);
while(j < l) upd(w[j ++], res, -1);
while(j > l) upd(w[-- j], res, 1);
ans1[id] = res - (r - l + 1);
ans2[id] = (r - l + 1LL) * (r - l);
d = std::__gcd(ans1[id], ans2[id]);
ans1[id] /= d, ans2[id] /= d;
}
for(int i = 0; i < m; i ++) printf("%lld/%lld\n", ans1[i], ans2[i]);
return 0;
}
P1972 [SDOI2009] HH的项链
莫队模板
点击查看代码
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 1e6 + 5;
int n, m, len, a[N], ans[N];
struct Query { int id, l, r; } querys[N];
int cnt[N];
int get_id(int x) { return (x - 1) / len + 1; }
void add(int x, int &res) {
if(!cnt[x]) res ++;
cnt[x] ++;
}
void del(int x, int &res) {
cnt[x] --;
if(!cnt[x]) res --;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
scanf("%d", &m);
len = sqrt(n);
for(int i = 0; i < m; i ++)
scanf("%d%d", &querys[i].l, &querys[i].r), querys[i].id = i;
std::sort(querys, querys + m, [&](const Query &x, const Query &y) {
if(get_id(x.l) != get_id(y.l)) return get_id(x.l) < get_id(y.l); // 先按块排序,在按右端点排序
return x.r < y.r; // 有时需要用 get_id是否为奇数来判断用 x.r<y.r还是x.r>y.r
});
for(int k = 0, i = 0, j = 1, res = 0; k < m; k ++) {
auto [id, l, r] = querys[k];
while(i < r) add(a[++ i], res);
while(i > r) del(a[i --], res);
while(j < l) del(a[j ++], res);
while(j > l) add(a[-- j], res);
ans[id] = res;
}
for(int i = 0; i < m; i ++) printf("%d\n", ans[i]);
return 0;
}
P1903 [国家集训队] 数颜色 / 维护队列
带修莫队 (l,r,t) 询问:排序方法:l编号,r编号,t 每次移动指针l,r,t, 移动t时分是否在块内的,若在块内
复杂度: a为块长 l: O(am+a*(n/a))=O(am+n) r: O(am+nn/a) t: O(nnt/aa)
a>=sqrt(n) 于是 r:O(am) 最终: a=三次根号(nt) 复杂度=三次根号(nnnnt)
点击查看代码
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 133340, M = 1000005;
int n, m, len, mq, mm;
int w[N], cnt[M], ans[N];
struct Query { int id, l, r, t; } queries[N];
struct Modify { int pos, val; } modifies[N];
int get_id(int x) { return (x - 1) / len + 1; }
void add(int x, int &res) {
if(!cnt[x]) res ++;
cnt[x] ++;
}
void del(int x, int &res) {
cnt[x] --;
if(!cnt[x]) res --;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", w + i);
for(int i = 0, a, b; i < m; i ++) {
static char op[2];
scanf("%s%d%d", op, &a, &b);
if(*op == 'Q') mq ++, queries[mq] = {mq, a, b, mm};
else mm ++, modifies[mm] = {a, b};
}
len = cbrt((double)n * std::max(1, mm)) + 1;
std::sort(queries + 1, queries + mq + 1, [&](const Query&x, const Query&y) {
int xl = get_id(x.l), xr = get_id(x.r), yl = get_id(y.l), yr = get_id(y.r);
if(xl != yl) return xl < yl;
if(xr != yr) return xr < yr;
return x.t < y.t;
});
for(int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++) {
auto [id, l, r, tm] = queries[k];
while(i < r) add(w[++ i], res);
while(i > r) del(w[i --], res);
while(j < l) del(w[j ++], res);
while(j > l) add(w[-- j], res);
while(t < tm) {
t ++;
if(modifies[t].pos >= j && modifies[t].pos <= i) // 在区间[j,i]内
del(w[modifies[t].pos], res), add(modifies[t].val, res);
std::swap(w[modifies[t].pos], modifies[t].val);
}
while(t > tm) {
if(modifies[t].pos >= j && modifies[t].pos <= i) // 在区间[j,i]内
del(w[modifies[t].pos], res), add(modifies[t].val, res);
std::swap(w[modifies[t].pos], modifies[t].val);
t --;
}
ans[id] = res;
}
for(int i = 1; i <= mq; i ++) printf("%d\n", ans[i]);
return 0;
}
历史研究
历史研究 回滚莫队
维护最大值(或任意不好删除的东西):
右端点在这个块: 暴力
右端点在块外: 下一个块的开头: 只有+ 在这个块内部的: 暴力
点击查看代码
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 100005;
typedef long long LL;
int n, m, len;
int w[N], cnt[N];
struct Query { int id, l, r; } queries[N];
int num[N], tot;
LL ans[N];
int get_id(int x) { return (x - 1) / len + 1; }
void add(int x, LL &res) {
cnt[x] ++;
res = std::max(res, cnt[x] * LL(num[x]));
}
int main() {
scanf("%d%d", &n, &m), len = sqrt(n);
for(int i = 1; i <= n; i ++) scanf("%d", w + i), num[++ tot] = w[i];
std::sort(num + 1, num + tot + 1), tot = std::unique(num + 1, num + tot + 1) - num - 1;
for(int i = 1; i <= n; i ++) w[i] = std::lower_bound(num + 1, num + tot + 1, w[i]) - num;
for(int i = 0; i < m; i ++) scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
std::sort(queries, queries + m, [&](const Query &x, const Query &y) {
if(get_id(x.l) != get_id(y.l)) return get_id(x.l) < get_id(y.l);
return x.r < y.r;
});
for(int x = 0; x < m; ) { // x表示询问的下标 每次枚举一个块
int y = x;
while(y < m && get_id(queries[y].l) == get_id(queries[x].l)) y ++;
int R = get_id(queries[x].l) * len - 1; // 这个块的右端点
while(x < y && queries[x].r <= R) { // 被这个块包含的区间: 暴力求
LL res = 0;
auto [id, l, r] = queries[x];
for(int k = l; k <= r; k ++) add(w[k], res);
ans[id] = res;
for(int k = l; k <= r; k ++) cnt[w[k]] --; // 清空
x ++;
}
LL res = 0;
int i = R, j = R + 1;
while(x < y) {
auto [id, l, r] = queries[x];
while(i < r) add(w[++ i], res);
LL res2 = res; // 备份
while(j > l) add(w[-- j], res); // 加入块内的
ans[id] = res;
while(j <= R) cnt[w[j ++]] --; // 清空
res = res2;
x ++;
}
memset(cnt, 0, sizeof(cnt)); // 清空
}
for(int i = 0; i < m; i ++) printf("%lld\n", ans[i]);
return 0;
}
P2709 小B的询问
点击查看代码
// 莫队模板
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 50005;
typedef long long LL;
int n, m, len, w[N], cnt[N]; // cnt维护出现个数
struct Query { int id, l, r; } queries[N];
LL ans1[N], ans2[N];
int get(int x) { return (x - 1) / len + 1; }
void upd(int x, LL &res, int dif) { // res为每个数出现次数平方和
res -= (LL)cnt[x] * cnt[x], cnt[x] += dif, res += (LL)cnt[x] * cnt[x];
}
int main() {
scanf("%d%d", &n, &m), len = sqrt(n);
for(int i = 1; i <= n; i ++) scanf("%d", w + i);
for(int i = 0; i < m; i ++) scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
std::sort(queries, queries + m, [&](const Query &x, const Query &y) {
if(get(x.l) != get(y.l)) return get(x.l) < get(y.l);
return x.r < y.r;
});
LL res = 0, d;
for(int k = 0, i = 0, j = 1; k < m; k ++) {
auto [id, l, r] = queries[k];
if(l == r) {
ans2[id] = 1;
continue;
}
while(i < r) upd(w[++ i], res, 1);
while(i > r) upd(w[i --], res, -1);
while(j < l) upd(w[j ++], res, -1);
while(j > l) upd(w[-- j], res, 1);
ans1[id] = res - (r - l + 1);
ans2[id] = (r - l + 1LL) * (r - l);
d = std::__gcd(ans1[id], ans2[id]);
ans1[id] /= d, ans2[id] /= d;
}
for(int i = 0; i < m; i ++) printf("%lld/%lld\n", ans1[i], ans2[i]);
return 0;
}