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

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。

相关文章

Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

《Docker镜像修改hosts及dockerfile修改hosts文件的实现方式》：本文主要介绍Docker镜像修改hosts及dockerfile修改hosts文件的实现方式,具有很好的参考价... 目录docker镜像修改hosts及dockerfile修改hosts文件准备 dockerfile 文
阅读更多...
Python基础文件操作方法超详细讲解(详解版)

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,：本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.
阅读更多...
Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战：从入门到进阶优化1. MyBatis
阅读更多...
Python实现无痛修改第三方库源码的方法详解

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很
阅读更多...
C#基础之委托详解(Delegate)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》：本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托（Multicast Delegates）4. 委托的用途事件处理回调函数LINQ
阅读更多...
Linux修改pip和conda缓存路径的几种方法

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓
阅读更多...
Linux修改pip临时目录方法的详解

Linux修改pip临时目录方法的详解

《Linux修改pip临时目录方法的详解》在Linux系统中,pip在安装Python包时会使用临时目录（TMPDIR）,但默认的临时目录可能会受到存储空间不足或权限问题的影响,所以本文将详细介绍如何... 目录引言一、为什么要修改 pip 的临时目录？1. 解决存储空间不足的问题2. 解决权限问题3. 提
阅读更多...
Linux文件名修改方法大全

Linux文件名修改方法大全

《Linux文件名修改方法大全》在Linux系统中,文件名修改是一个常见且重要的操作,文件名修改可以更好地管理文件和文件夹,使其更具可读性和有序性,本文将介绍三种在Linux系统下常用的文件名修改方法... 目录一、引言二、使用mv命令修改文件名三、使用rename命令修改文件名四、mv命令和rename命
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
Linux下修改hostname的三种实现方式

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》：本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1：修改配置文件方法2：hFvEWEostnamectl命
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2