莫队入门(基础莫队，带修改的莫队，树上莫队..)

2024-03-20 16:58
文章标签 基础 入门 修改 树上 莫队 ..

本文主要是介绍莫队入门(基础莫队，带修改的莫队，树上莫队..)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学习于胡小兔博客 自为风月马前卒博客

不带修改莫队：

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e6+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
struct node{int id,l,r;
}q[N];
int n,m,num[N],a[N],ans[N],base,sum=0;
il int ka(int x){return (x-1)/base+1;}
il bool cmp(node x,node y){return ka(x.l)==ka(y.l)?x.r<y.r:x.l<y.l;
}
il void add(int x){if(!num[x]) sum++;num[x]++;
}
il void del(int x){num[x]--;if(!num[x]) sum--;
}
int main(){
//	std::ios::sync_with_stdio(0);cin.tie(0);read(n);for(int i=1;i<=n;++i) read(a[i]);read(m);for(int i=1;i<=m;++i) read(q[i].l),read(q[i].r),q[i].id=i;base=sqrt(n)+1;sort(q+1,q+m+1,cmp);int l=1,r=0;for(int i=1;i<=m;++i){while(l<q[i].l) del(a[l++]);while(l>q[i].l) add(a[--l]);while(r<q[i].r) add(a[++r]);while(r>q[i].r) del(a[r--]);ans[q[i].id]=sum;}for(int i=1;i<=m;++i) printf("%d\n",ans[i]);return 0;
}

带修改莫队：加入时间轴即可

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e6+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,a[N],ans[N],num[N],base,sum=0;
int qid=0,cid=0,cur=0,l,r;
struct Q{int id,l,r;//id即为时间轴 
}qu[N];
il int ka(int x){return (x-1)/base+1;}
il bool cmp(Q x,Q y){if(ka(x.l)!=ka(y.l)) return x.l<y.l;else if(ka(x.r)!=ka(y.r)) return x.r<y.r;else return x.id<y.id;
}
struct C{int id,pos,val,pre;
}cg[N];
il void add(int x){if(!num[x]) sum++;num[x]++;
}
il void del(int x){num[x]--;if(!num[x]) sum--;
}
il void preadd(int x){//增加修改操作 if(cg[x].pos>=l && cg[x].pos<=r){num[a[cg[x].pos]]--;if(!num[a[cg[x].pos]]) sum--;}cg[x].pre=a[cg[x].pos];a[cg[x].pos]=cg[x].val;if(cg[x].pos>=l && cg[x].pos<=r){if(!num[a[cg[x].pos]]) sum++;num[a[cg[x].pos]]++;}
}
il void predel(int x){//撤销修改操作 if(cg[x].pos>=l && cg[x].pos<=r){num[a[cg[x].pos]]--;if(!num[a[cg[x].pos]]) sum--;}a[cg[x].pos]=cg[x].pre;if(cg[x].pos>=l && cg[x].pos<=r){if(!num[a[cg[x].pos]]) sum++;num[a[cg[x].pos]]++;}
}
il void solve(int time){while(cur<cid && cg[cur+1].id<time) preadd(++cur);while(cur>=1 && cg[cur].id>time) predel(cur--);
}
int main(){
//	std::ios::sync_with_stdio(0);cin.tie(0);read(n),read(m);base=sqrt(n)+1;for(int i=1;i<=n;++i) read(a[i]);char op[2];for(int i=1,x,y;i<=m;++i){scanf("%s",op);read(x),read(y);if(op[0]=='Q')	qu[++qid]={i,x,y};else cg[++cid]={i,x,y,0};}sort(qu+1,qu+qid+1,cmp);l=1,r=0;for(int i=1;i<=qid;++i){solve(qu[i].id);while(l<qu[i].l) del(a[l++]);while(l>qu[i].l) add(a[--l]);while(r<qu[i].r) add(a[++r]);while(r>qu[i].r) del(a[r--]);ans[qu[i].id]=sum;}for(int i=1;i<=m;++i){if(ans[i]) printf("%d\n",ans[i]);	}return 0;
}

树上莫队前置技能：（简单分块）

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,B,stk[N*2],cap[N],bel[N],top=0,cnt=0;
vector<int> G[N];
il void dfs(int x,int f){int st=top,to;for(int i=0;i<SZ(G[x]);++i){to=G[x][i];if(to==f) continue;dfs(to,x);if(top-st>=B){cap[++cnt]=x;while(top>st) bel[stk[top--]]=cnt;}}stk[++top]=x;
}
int main(){
//	std::ios::sync_with_stdio(0);cin.tie(0);scanf("%d%d",&n,&B);for(int i=1,x,y;i<=n-1;++i){scanf("%d%d",&x,&y);G[x].pb(y),G[y].pb(x);}	dfs(1,0);while(top) bel[stk[top--]]=cnt;printf("%d\n",cnt);for(int i=1;i<=n;++i) printf("%d ",bel[i]);printf("\n");for(int i=1;i<=cnt;++i) printf("%d ",cap[i]);return 0;
}

这种还没怎么看懂，例题是带修改的莫队

 

从第二篇博客学习了用括号序列解决的方法

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e5+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,dep[N],fa[N][25],lg[N];
int st[N],ed[N],pot[N],tot=0;
int a[N],sa[N],block,ka[N*2];
int num[N],sum=0,ans[N];
bool vis[N];
vector<int> G[N];
il void init(){lg[0]=-1,block=sqrt(n)+1;for(int i=1;i<N;++i) lg[i]=lg[i>>1]+1;sort(sa+1,sa+n+1);int sz=unique(sa+1,sa+n+1)-sa-1;for(int i=1;i<=n;++i) a[i]=lower_bound(sa+1,sa+sz+1,a[i])-sa;for(int i=1,len=n*2;i<=len;++i) ka[i]=i/block+1;
}
il void dfs(int np,int f){dep[np]=dep[f]+1,fa[np][0]=f;st[np]=++tot,pot[tot]=np;for(int i=1;i<=lg[dep[np]]+1;++i) fa[np][i]=fa[fa[np][i-1]][i-1];for(auto to:G[np]){if(to!=f) dfs(to,np);}ed[np]=++tot,pot[tot]=np;
}
il int getlca(int u,int v){if(dep[u]<dep[v]) swap(u,v);while(dep[u]!=dep[v])	u=fa[u][lg[dep[u]-dep[v]]];if(u==v) return u;for(int i=lg[dep[u]];i>=0;--i){if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];}return fa[u][0];
}
struct Q{int id,l,r,lca;
}q[N];
il bool cmp(Q x,Q y){return ka[x.l]==ka[y.l]?x.r<y.r:x.l<y.l;
}
il void add(int x){if(!num[x]) sum++;num[x]++;
}
il void del(int x){num[x]--;if(!num[x]) sum--;
}
il void cg(int x){if(vis[x]) del(a[x]);else add(a[x]);vis[x]^=1;
}
int main(){
//	std::ios::sync_with_stdio(0);cin.tie(0);read(n),read(m);for(int i=1;i<=n;++i) read(a[i]),sa[i]=a[i];init();for(int i=1,x,y;i<=n-1;++i){read(x),read(y);G[x].pb(y),G[y].pb(x);}dfs(1,0);for(int i=1,x,y;i<=m;++i){read(x),read(y);if(st[x]>st[y]) swap(x,y);int lca=getlca(x,y);if(lca==x) q[i]={i,st[x],st[y],0};else q[i]={i,ed[x],st[y],lca};//	cout<<"MQ "<<i<<" "<<q[i].l<<" "<<q[i].r<<" "<<q[i].lca<<endl; }sort(q+1,q+m+1,cmp);int l=1,r=0;for(int i=1;i<=m;++i){//	cout<<"solve "<<q[i].l<<" "<<q[i].r<<endl;while(l<q[i].l) cg(pot[l++]);while(l>q[i].l) cg(pot[--l]);while(r<q[i].r) cg(pot[++r]);while(r>q[i].r) cg(pot[r--]);if(q[i].lca) cg(q[i].lca);ans[q[i].id]=sum;if(q[i].lca) cg(q[i].lca);}for(int i=1;i<=m;++i) printf("%d\n",ans[i]);return 0;
}

 

这篇关于莫队入门(基础莫队，带修改的莫队，树上莫队..)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/830138。

相关文章

python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
Spring WebClient从入门到精通

Spring WebClient从入门到精通

《SpringWebClient从入门到精通》本文详解SpringWebClient非阻塞响应式特性及优势,涵盖核心API、实战应用与性能优化,对比RestTemplate,为微服务通信提供高效解决... 目录一、WebClient 概述1.1 为什么选择 WebClient？1.2 WebClient 与
阅读更多...
Spring Boot 与微服务入门实战详细总结

Spring Boot 与微服务入门实战详细总结

《SpringBoot与微服务入门实战详细总结》本文讲解SpringBoot框架的核心特性如快速构建、自动配置、零XML与微服务架构的定义、演进及优缺点,涵盖开发环境准备和HelloWorld实战... 目录一、Spring Boot 核心概述二、微服务架构详解1. 微服务的定义与演进2. 微服务的优缺点三
阅读更多...
从入门到精通详解LangChain加载HTML内容的全攻略

从入门到精通详解LangChain加载HTML内容的全攻略

《从入门到精通详解LangChain加载HTML内容的全攻略》这篇文章主要为大家详细介绍了如何用LangChain优雅地处理HTML内容,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录引言：当大语言模型遇见html一、HTML加载器为什么需要专门的HTML加载器核心加载器对比表二
阅读更多...
从入门到进阶讲解Python自动化Playwright实战指南

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习
阅读更多...
从入门到精通MySQL联合查询

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》：本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
从入门到精通MySQL 数据库索引(实战案例)

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么？能干嘛？核心作用：二、索引的 4 种主要类型（附通俗例子）1. BTree 索引（
阅读更多...
Redis 配置文件使用建议redis.conf 从入门到实战

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么？二、命令行方式传参（适用于测试）三、运行时动态修改配置（不重启服务
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2