基础莫队算法(上)

简介: 笔记

基础莫队


适用于求区间内不同数的个数问题


排序方式


如果当前两个区间左端点在同一个奇数块,那么按右端点递减排序,否则按右端点递增排序


分块大小和时间复杂度

10.png


模板代码

#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize(2)
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 50010, M = 200010, S = 1000010;
int n, m;
int a[N], cnt[S], ans[M];
int block;
struct Node {
    int id, l, r;
}node[M];
bool cmp(const Node& a, const Node& b) {
    // 如果当前两个区间左端点在同一个奇数块,那么按右端点递减排序,否则按右端点递增排序
    int l = a.l / block, r = b.l / block;
    return l ^ r ? l < r : (l & 1 ? a.r < b.r : a.r > b.r);
}
void add(int x, int& res) {
    cnt[x]++;
    if (cnt[x] == 1)res++;
}
void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])res--;
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int l, r; scanf("%d%d", &l, &r);
        node[i] = { i,l,r };
    }
    block = n / sqrt(n);
    sort(node + 1, node + 1 + m, cmp);
    int i = 0, j = 1;
    int res = 0;
    for (int k = 1; k <= m; ++k) {// 对排序后的查询进行计算
        int l = node[k].l;
        int r = node[k].r;
        // 将add del函数 通过运算优先级优化成常数
        while (i < r)res += !cnt[a[++i]]++; 
        while (i > r)res -= !--cnt[a[i--]];
        while (j < l)res -= !--cnt[a[j++]];
        while (j > l)res += !cnt[a[--j]]++;
        ans[node[k].id] = res;
    }
    for (int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}
signed main() {
    // int _; cin >> _;
    // while (_--)
    solve();
    return 0;
}


HH的项链

题意

HH 有一串由各种漂亮的贝壳组成的项链。


HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。


HH 不断地收集新的贝壳,因此他的项链变得越来越长。


有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?


这个问题很难回答,因为项链实在是太长了。


于是,他只好求助睿智的你,来解决这个问题。


思路

莫队模板题


数据范围


11.png

与求某区间内不同数的思路相同,先用莫队思想把查询区间排序,与上题(HH的项链)不同的是,将 l 初始为 0,r初始为 n + 1,最初包括整个区间。这样每次用 l,r与当前查询的 lr比较。


例如,如果e[i].r


l 从0 开始类似。


相应的add del 操作也要进行更改,因为 r 变大或者 l 变小时,区间里的数是减少的。r 变小或者 l 变大时,区间里的数是增加的。


代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1e5 + 10;
int n, m;
int a[N], ans[N], cnt[N];
int block;
struct Node {
    int id, l, r;
}node[N];
bool cmp(const Node& a, const Node& b) {
    if (a.l / block == b.l / block)return a.r < b.r;
    return a.l / block < b.l / block;
}
void add(int x, int& res) {
    cnt[x] ++;
    if (cnt[x] == 1)res++;
}
void del(int x, int& res) {
    cnt[x]--;
    if (!cnt[x])res--;
}
void solve() {
    while (~scanf("%d%d", &n, &m)) {
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
        block = sqrt(n);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &node[i].l, &node[i].r);
            node[i].id = i;
        }
        sort(node + 1, node + 1 + m, cmp);
        int l = 0, r = n + 1;
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            int id = node[i].id;
            while (r < node[i].r)del(a[r++], res);
            while (r > node[i].r)add(a[--r], res);
            while (l < node[i].l)add(a[++l], res);
            while (l > node[i].l)del(a[l--], res);
            ans[id] = res;
        }
        for (int i = 1; i <= m; ++i)printf("%d\n", ans[i]);
    }
}
signed main() {
    // int _; cin >> _;
    // while (_--)
    solve();
    return 0;
}


带修莫队


适用于查询区间内不同数的个数,加修改区间内某个数

排序方式:

bool cmp(Query& a, Query& b) {
    return (a.l / block) ^ (b.l / block) ? (a.l / block < b.l / block) : (a.r / block) ^ (b.r / block) ? (a.r / block < b.r / block) : (a.t < b.t);
}


如果左端点块号奇偶性不同,按照块号递增排序


否则 如果右端点奇偶性不同,按照块号递增排序


否则 按照时间戳递增排序


分块大小和时间复杂度

12.png


模板代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
// template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 2e5 + 10, S = 1e6 + 10;
int n, m;
int cnt[S]; // 记录每个数出现的次数
int a[N]; // 原数组
int mq, mc; // 询问和修改的次数
int block; // 分块的大小
int ans[N]; // 记录每个询问的答案
struct Query { // 询问操作结构体
    int id, l, r, t;
    // id 表示询问的先后顺序
    // t 表示 时间戳 即离它最近的修改操作的编号
}q[N];
struct Modify { // 修改操作结构体
    // 将 l 位置上的数修改成 r
    int l, r;
}c[N];
bool cmp(Query& a, Query& b) { // 排序比较函数
    return (a.l / block) ^ (b.l / block) ? (a.l / block < b.l / block) : (a.r / block) ^ (b.r / block) ? (a.r / block < b.r / block) : (a.t < b.t);
}
void del(int x,int &res){ // 删除操作
    cnt[x]--;
    if (!cnt[x])res--;
}
void add(int x, int& res) { // 增加操作
    if (!cnt[x])res++;
    cnt[x]++;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        //离线存储所有询问和修改操作
        if (op[0] == 'Q') q[++mq] = { mq,l,r,mc };
        else c[++mc] = { l,r };
    }
    block = cbrt((double)n * n); // 计算分块的大小
    sort(q + 1, q + 1 + mq, cmp);
    int l = 1, r = 0, t = 0, res = 0;
    for (int k = 1; k <= m; ++k) {
        int id = q[k].id;
        // 水平区间上进行移动
        while (l < q[k].l)res -= !--cnt[a[l++]];
        while (l > q[k].l)res += !cnt[a[--l]]++;
        while (r < q[k].r)res += !cnt[a[++r]]++;
        while (r > q[k].r)res -= !--cnt[a[r--]];
        // 时间戳上进行移动
        // t 表示 1-t 的修改操作已经执行
        while (t < q[k].t) {
            // 需要将时间戳往后移动
            t++;
            // 如果需要修改的数在当前 [l, r] 区间内
            // 将被修改的数删除,将修改成的数加入
            if (c[t].l >= l && c[t].l <= r) {
                res -= !--cnt[a[c[t].l]];
                res += !cnt[c[t].r]++;
            }
            // 每次操作将两个数 swap 一下,就不用存当前数被修改成了哪个数
            swap(a[c[t].l], c[t].r);
        }
        while (t > q[k].t) {
            // 因为 t 较大  所以要先把当前的 t 删除 再 t--
            if (c[t].l >= l && c[t].l <= r) {
                res -= !--cnt[a[c[t].l]];
                res += !cnt[c[t].r]++;
            }
            swap(a[c[t].l], c[t].r);
            t--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= mq; ++i)printf("%d\n", ans[i]);
}
signed main() {
    // int _; cin >> _;
    // while (_--)
        solve();
    return 0;
}



相关实践学习
5分钟轻松打造应对流量洪峰的稳定商城交易系统
本实验通过SAE极速部署一个微服务电商商城,同时结合RocketMQ异步解耦、削峰填谷的能力,带大家体验面对流量洪峰仍旧稳定可靠的商城交易系统!
消息队列 MNS 入门课程
1、消息队列MNS简介 本节课介绍消息队列的MNS的基础概念 2、消息队列MNS特性 本节课介绍消息队列的MNS的主要特性 3、MNS的最佳实践及场景应用 本节课介绍消息队列的MNS的最佳实践及场景应用案例 4、手把手系列:消息队列MNS实操讲 本节课介绍消息队列的MNS的实际操作演示 5、动手实验:基于MNS,0基础轻松构建 Web Client 本节课带您一起基于MNS,0基础轻松构建 Web Client
目录
打赏
0
0
0
0
1
分享
相关文章
如何在宝塔mysql修改掉3306端口
在宝塔面板管理MySQL时,默认使用3306端口。为提升安全或避免冲突,可修改端口。步骤如下:1. 登录宝塔面板;2. 进入数据库管理;3. 找到并编辑my.cnf配置文件,修改`port`值;4. 保存并重启MySQL服务;5. 开放防火墙新端口;6. 测试连接。具体命令和流程图详见正文。
249 1
探索微服务架构下的服务治理策略
【5月更文挑战第28天】在当今快速发展的云计算和容器化技术浪潮中,微服务架构凭借其灵活性、可扩展性和容错性等优势成为众多企业转型的首选。然而,随着服务的不断拆分与细化,服务治理成为了确保系统稳定性和高效运作的关键挑战。本文将深入分析微服务架构中的服务治理策略,探讨如何通过合理的设计和技术选型来提升系统的可维护性和性能,同时保障服务的高可用性和安全。
133 0
1分钟认识:人工智能claude AI _详解CLAUDE在国内怎么使用
Claude AI 是 Anthropic 开发的先进对话式 AI 模型,以信息论之父克劳德·香农命名,体现了其在信息处理和生成方面的卓越能力
C enum(枚举)详解
在C语言中,`enum`(枚举类型)允许用户定义包含命名整数常量的数据类型,提高了代码的可读性和可维护性。通过关键字`enum`定义枚举,如`enum Color {RED, GREEN, BLUE}`。枚举值默认从0开始递增,也可自定义。枚举类型实际上是整型的别名,可用于简化代码并限制变量的具体取值范围。
421 15
Redis 内存突增时,如何定量分析其内存使用情况
【9月更文挑战第21天】当Redis内存突增时,可采用多种方法分析内存使用情况:1)使用`INFO memory`命令查看详细内存信息;2)借助`redis-cli --bigkeys`和RMA工具定位大键;3)利用Prometheus和Grafana监控内存变化;4)优化数据类型和存储结构;5)检查并调整内存碎片率。通过这些方法,可有效定位并解决内存问题,保障Redis稳定运行。
587 4
|
11月前
|
SFNC —— 图像格式控制(三)(下)
SFNC —— 图像格式控制(三)
291 3
问题记录:Redhat6.5 网卡配置变更后,Eth0变为Eth1
Red Hat Enterprise Linux 6.5(Redhat 6.5)尽管是一个较旧的操作系统版本,仍然在许多企业环境中发挥着重要作用。然而,老旧的系统并不免于技术挑战。例如,本文将探讨一个在修改网卡配置后遇到的一个奇怪问题:在网卡配置变更后,原本是eth0的网卡名称变更为了eth1。
问题记录:Redhat6.5 网卡配置变更后,Eth0变为Eth1
【Azure Redis 缓存】云服务Worker Role中调用StackExchange.Redis,遇见莫名异常(RedisConnectionException: UnableToConnect on xxx 或 No connection is available to service this operation: xxx)
【Azure Redis 缓存】云服务Worker Role中调用StackExchange.Redis,遇见莫名异常(RedisConnectionException: UnableToConnect on xxx 或 No connection is available to service this operation: xxx)
183 0
【C/C++ 标准的发展】C/C++ 语言标准的历史和演变
【C/C++ 标准的发展】C/C++ 语言标准的历史和演变
577 3
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问