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

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。

相关文章

Nginx 413修改上传文件大小限制的方法详解

Nginx 413修改上传文件大小限制的方法详解

《Nginx413修改上传文件大小限制的方法详解》在使用Nginx作为Web服务器时,有时会遇到客户端尝试上传大文件时返回​​413RequestEntityTooLarge​​... 目录1. 理解 ​​413 Request Entity Too Large​​ 错误2. 修改 Nginx 配置2.1
阅读更多...
SpringBoot基础框架详解

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2
阅读更多...
Python对PDF书签进行添加,修改提取和删除操作

Python对PDF书签进行添加,修改提取和删除操作

《Python对PDF书签进行添加,修改提取和删除操作》PDF书签是PDF文件中的导航工具,通常包含一个标题和一个跳转位置,本教程将详细介绍如何使用Python对PDF文件中的书签进行操作... 目录简介使用工具python 向 PDF 添加书签添加书签添加嵌套书签Python 修改 PDF 书签Pytho
阅读更多...
Spring Boot集成SLF4j从基础到高级实践(最新推荐)

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面（Facade）,不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4
阅读更多...
Spring Boot集成Logback终极指南之从基础到高级配置实战指南

Spring Boot集成Logback终极指南之从基础到高级配置实战指南

《SpringBoot集成Logback终极指南之从基础到高级配置实战指南》Logback是一个可靠、通用且快速的Java日志框架,作为Log4j的继承者,由Log4j创始人设计,：本文主要介绍... 目录一、Logback简介与Spring Boot集成基础1.1 Logback是什么？1.2 Sprin
阅读更多...
POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

《POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能》ApachePOI是一个流行的Java库,用于处理MicrosoftOffice格式文件,提供丰富API来创建、读取和修改O... 目录前言:Apache POIEasyPoiEasyExcel一、EasyExcel1.1、核心特性
阅读更多...
MySQL复合查询从基础到多表关联与高级技巧全解析

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言：1.基本查询回顾：1.1.查询工资高于500或岗位为MANAGER的雇员，同时还要满足他们的姓名首字母为大写的J1.2.按照部门
阅读更多...
Python中模块graphviz使用入门

Python中模块graphviz使用入门

《Python中模块graphviz使用入门》graphviz是一个用于创建和操作图形的Python库,本文主要介绍了Python中模块graphviz使用入门,具有一定的参考价值,感兴趣的可以了解一... 目录1.安装2. 基本用法2.1 输出图像格式2.2 图像style设置2.3 属性2.4 子图和聚
阅读更多...
Android Mainline基础简介

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline？Android Mainline 的工作原理关键
阅读更多...
mysql的基础语句和外键查询及其语句详解(推荐)

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》：本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2