首页 > 其他分享 >莫队简单入门

莫队简单入门

时间：2024-09-06 16:37:42浏览次数：14  
标签：cnt 入门 int res pos ++ 简单 莫队 define

莫队简单入门

补最近一场DIV.4 时遇到一道需要求区间众数的题目，完善一下技能树。

简介：

莫队是一种解决离线区间询问问题的方法。能够在 \(O(n\sqrt{n})\) 的时间复杂度内求出所有询问的答案。

大致流程：

1.将所有数据分块。有时需要离散化。

2.将所有询问离线，并排序。

3.对于区间 \([l,r]\) 按照 \(l\) 所在块的编号为第一关键字， \(r\) 为第二关键字从小到大排序。

4.处理所有询问，通过区间 \([l,r]\) 的答案拓展到 \([l-1,r],[l+1,r],[l,r+1],[l,r-1]\) 的答案。

代码框架：

struct Q{
  int l,r,id;
};
void Showball(){
  int n,m;
  cin>>n>>m;
  //分块
  int siz=sqrt(n);
  vector<int> a(n+1),pos(n+1),cnt(n+1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
    pos[i]=i/siz;
  }  
  vector<Q> q(m);
  for(int i=0;i<m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(all(q),[&](Q x,Q y){
    return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
  });

  int l=1,r=0;
  LL res=0;
  vector<LL> ans(m);

  auto Add=[&](int x){
    
  };
  auto Sub=[&](int x){
    
  };
  for(int i=0;i<m;i++){
    while(q[i].l<l) Add(--l);
    while(q[i].r>r) Add(++r);
    while(q[i].l>l) Sub(l++);
    while(q[i].r<r) Sub(r--);
    ans[q[i].id]=-res;
  }
  for(auto x:ans) cout<<x<<endl;
}

例题

洛谷P2709 小B的询问

题目链接

题意：

给你一个长度为 \(n\) 的序列，一共 \(m\) 次询问，查询区间所有内所有数出现次数的平方和。

思路：

莫队模板题，那么我们只需要去思考如何去维护 \(Add\) 和 \(Sub\) 函数即可。

很显然，\(Add\) 函数只需要减去原本的贡献，然后 \(cnt[a[x]]++\) 。再加上新的贡献即可。

\(Sub\) 函数同理即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

struct Q{
  int l,r,id;
};
void Showball(){
  int n,m,k;
  cin>>n>>m>>k;
  //分块
  int siz=sqrt(n);
  vector<int> a(n+1),pos(n+1),cnt(n+1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
    pos[i]=i/siz;
  }  
  vector<Q> q(m);
  for(int i=0;i<m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(all(q),[&](Q x,Q y){
    return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
  });

  int l=1,r=0;
  LL res=0;
  vector<LL> ans(m);

  auto Add=[&](int x){
    res-=1LL*cnt[a[x]]*cnt[a[x]];
    cnt[a[x]]++;
    res+=1LL*cnt[a[x]]*cnt[a[x]];
  };
  auto Sub=[&](int x){
    res-=1LL*cnt[a[x]]*cnt[a[x]];
    cnt[a[x]]--;
    res+=1LL*cnt[a[x]]*cnt[a[x]];
  };
  for(int i=0;i<m;i++){
    while(q[i].l<l) Add(--l);
    while(q[i].r>r) Add(++r);
    while(q[i].l>l) Sub(l++);
    while(q[i].r<r) Sub(r--);
    ans[q[i].id]=res;
  }
  for(auto x:ans) cout<<x<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

洛谷1997 faebdc的烦恼

题目链接

题意：

给你一个长度为 \(n\) 的序列，\(q\) 次询问，询问区间内众数的出现次数。

思路：

莫队，考虑 \(Add\) 函数，我们依旧需要维护 \(cnt\) 数组表示每个数出现的数量。那么，只需要 \(cnt[a[x]]++\)。

如果这个值超过了原本的最值，更新即可。对于 \(Sub\) 函数，稍微复杂一些，\(a[x]\) 出现的数量减一，如果原本 \(a[x]\) 的数量很少，那么没有影响。如果 \(a[x]\) 的数量是最多的。有两种情况：

\(a[x]\) 是唯一数量最多的。那么答案就要减一。

\(a[x]\) 不是唯一数量最多的，那么数量最多的数量就要减一。

因此，我们需要额外维护一个出现数量为 \(x\) 的数有多少个的数组 \(sum\)。

注意值域存在负数，那么我们全部平移一下即可。数组开两倍。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

struct Q{
  int l,r,id;
};
void Showball(){
  int n,m;
  cin>>n>>m;
  //分块
  int siz=sqrt(n);
  vector<int> a(n+1),pos(n+1),cnt(N),sum(n+1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i]+=100001;
    pos[i]=i/siz;
  }  
  vector<Q> q(m);
  for(int i=0;i<m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(all(q),[&](Q x,Q y){
    return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
  });

  int l=1,r=0;
  LL res=0;
  vector<LL> ans(m);

  auto Add=[&](int x){
    sum[++cnt[a[x]]]++;
    if(cnt[a[x]]>res) res=cnt[a[x]];
    return;
  };
  auto Sub=[&](int x){
    if(sum[cnt[a[x]]]==1&&cnt[a[x]]==res) res--;
    sum[cnt[a[x]]--]--;
    return;
  };
  for(int i=0;i<m;i++){
    while(q[i].l<l) Add(--l);
    while(q[i].r>r) Add(++r);
    while(q[i].l>l) Sub(l++);
    while(q[i].r<r) Sub(r--);
    ans[q[i].id]=res;
  }
  for(auto &x:ans) cout<<x<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

双倍经验 洛谷P3709 大爷的字符串题

题目链接

和上面那题一样，多了一步离散化即可。

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

struct Q{
  int l,r,id;
};
void Showball(){
  int n,m;
  cin>>n>>m;
  //分块
  int siz=sqrt(n);
  vector<int> a(n+1),pos(n+1),sum(n+1),cnt(n+1);
  vector<int> v;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    v.pb(a[i]);
    pos[i]=i/siz;
  }
  sort(all(v));
  v.erase(unique(all(v)),v.end());
  for(int i=1;i<=n;i++) a[i]=lower_bound(all(v),a[i])-v.begin()+1;  
  vector<Q> q(m);
  for(int i=0;i<m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(all(q),[&](Q x,Q y){
    return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
  });

  int l=1,r=0;
  LL res=0;
  vector<LL> ans(m);

  auto Add=[&](int x){
    sum[++cnt[a[x]]]++;
    if(cnt[a[x]]>res) res=cnt[a[x]];
    return;
  };
  auto Sub=[&](int x){
    if(sum[cnt[a[x]]]==1&&cnt[a[x]]==res) res--;
    sum[cnt[a[x]]--]--;
    return;
  };
  for(int i=0;i<m;i++){
    while(q[i].l<l) Add(--l);
    while(q[i].r>r) Add(++r);
    while(q[i].l>l) Sub(l++);
    while(q[i].r<r) Sub(r--);
    ans[q[i].id]=-res;
  }
  for(auto &x:ans) cout<<x<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

CF 2009 G1. Yunli's Subarray Queries (easy version)

题目链接

题意：

给你一个长度为 \(n\) 的序列，你可以任意次修改每个数为任何值。\(q\) 次询问，询问将给定区间的值变成一次连续递增的至少需要多少次操作。

思路：

很经典的Trik，我们只需要将每个数加上 \(n-i+1\) ，那么问题就变成了求解区间众数问题。直接套用上面题的方法即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

struct Q{
  int l,r,id;
};
void Showball(){
  int n,k,m;
  cin>>n>>k>>m;
  //分块
  int siz=sqrt(n);
  vector<int> a(n+1),pos(n+1),sum(n+1),cnt(n<<1|1);
  for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i]+=n-i+1;
    pos[i]=i/siz;
  }
  vector<Q> q(m);
  for(int i=0;i<m;i++){
    cin>>q[i].l>>q[i].r;
    q[i].id=i;
  }
  sort(all(q),[&](Q x,Q y){
    return pos[x.l]!=pos[y.l]?pos[x.l]<pos[y.l]:(pos[x.l]&1?x.r<y.r:x.r>y.r);
  });

  int l=1,r=0;
  LL res=0;
  vector<LL> ans(m);

  auto Add=[&](int x){
    sum[++cnt[a[x]]]++;
    if(cnt[a[x]]>res) res=cnt[a[x]];
    return;
  };
  auto Sub=[&](int x){
    if(sum[cnt[a[x]]]==1&&cnt[a[x]]==res) res--;
    sum[cnt[a[x]]--]--;
    return;
  };
  for(int i=0;i<m;i++){
    while(q[i].l<l) Add(--l);
    while(q[i].r>r) Add(++r);
    while(q[i].l>l) Sub(l++);
    while(q[i].r<r) Sub(r--);
    ans[q[i].id]=q[i].r-q[i].l+1-res;
  }
  for(auto &x:ans) cout<<x<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

标签：cnt,入门,int,res,pos,++,简单,莫队,define
From： https://www.cnblogs.com/showball/p/18400510

相关文章

  • 数据库简单概述
    什么是数据库？数据库(DatabaseDB)是按照数据结构来组织、存储和管理数据的仓库(存储数据的仓库)，它产生于距今六十多年前，随着信息技术和市场的发展，特别是二十世纪九十年代以后，数据管理不再仅仅是存储和管理数据，而转变成用户所需要的各种数据管理的方式。数据库有很多种类型，从最简......
  • 【C++】简单易懂的vector迭代器
    一、迭代器的本质vector的迭代器本质上就是一个被封装的指针。迭代器的用法和指针的用法十分相似，就是一个像指针的假指针，我们不妨把迭代器看作一个伪指针。二、迭代器的使用句式（可以看到迭代器和指针很像）：迭代器有四种：1、正向迭代器：容器名<类型>::iterator迭代器名2、常......
  • 【AI大模型】AI大模型热门关键词解析与核心概念入门
    关注公众号ai技术星球回复88即可领取技术学习资料目录导航热门AI大模型关键词解析热门AI大模型关键词解析大模型代码语言：javascript复制-"大模型"的是大型的人工智能模型，特别是在深度学习领域中。这些模型因其庞大的参数数量、复杂的网络结构和在多种任务上的......
  • linux脚本入门编写
    平时一些重复率比较高的linux命令可以写成脚本来操作这样会大大减少操作时间,提升工作效率#!/bin/bash#删除名为sdss-base-system的容器dockerrm-fsdss-base-system#删除名为sdss-base-system的镜像dockerrmisdss-base-system#使用当前目录的Dockerfi......
  • 简单实现限流中间件
    本文由ChatMoney团队出品引言在现代Web应用开发中，限流是一个重要的概念，它能够保护服务器免受流量攻击，确保服务的稳定性和可用性。Go语言以其高性能和并发处理能力在后端服务开发中广受欢迎。Gin是一个使用Go语言编写的Web框架，以其简洁和高效著称。在Gin框架中，通过中间件实现......
  • 车载以太网交换机入门基本功（4）—优先级设计与VLAN测试
        在《车载以太网交换机入门基本功（3）》介绍了交换机端口属性和实际的VLAN转发过程。但是，当存在多个待转发的报文时，既要考虑到报文的及时性，又要考虑到转发效率，因此，如何进行有效调度就成了重要问题。一个解决办法是进行优先级设计。优先级设计    优先级设计包括报......
  • 实现中间件限流的简单方法
    本文由ChatMoney团队出品引言在现代Web应用开发中，限流是一个重要的概念，它能够保护服务器免受流量攻击，确保服务的稳定性和可用性。Go语言以其高性能和并发处理能力在后端服务开发中广受欢迎。Gin是一个使用Go语言编写的Web框架，以其简洁和高效著称。在Gin框架中，通过中间件实现......
  • 快速掌握AI算法基础：对于AI行业的“共同语言”入门指南
    对于非相关专业的AI产品或者想要转型AI产品的同学，算法知识晦涩难懂，如何用很短的时间快速入门，让你在AI领域更加游刃有余。 一、机器学习、深度学习、强化学习的定义1、机器学习（MachineLearning,ML）机器学习是人工智能（AI）的一个分支领域，旨在通过计算机系统的学习和自动化推......
  • 有关API接口的介绍及简单的API接口代码示例
    在当今数字化时代，应用程序不再孤立存在。它们通过API（应用程序编程接口）相互连接，共享数据和功能。API是现代软件开发中不可或缺的一部分，它允许不同的软件系统相互通信，实现数据的交换和业务逻辑的集成。一、API接口的基本概念API接口是一种预定义的函数或协议，它允许不同的软件应用......
  • 黑神话：悟空电脑太卡？配置不够？ToDesk云电脑入门新手教程
    许多玩家在玩《黑神话：悟空》时会遭遇硬件配置不足导致的游戏卡顿、画面不流畅等问题。其实这个难题很好解决，用ToDesk云电脑即可迎刃而解。即使你的本地电脑配置不高，也能享受到流畅的游戏体验。以下是一个针对新手的ToDesk云电脑入门教程，教你轻松解决配置不足的难题。什么是ToD......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99