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

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修改字符串值的三种方法

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法：第二种方法：第三种方法：在python中，字符串对象是不可变类型，所以我们没办法直接
阅读更多...
Mysql8.0修改配置文件my.ini的坑及解决

Mysql8.0修改配置文件my.ini的坑及解决

《Mysql8.0修改配置文件my.ini的坑及解决》使用记事本直接编辑my.ini文件保存后,可能会导致MySQL无法启动,因为MySQL会以ANSI编码读取该文件,解决方法是使用Notepad++... 目录Myhttp://www.chinasem.cnsql8.0修改配置文件my.ini的坑出现的问题
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
数论入门整理（updating）

数论入门整理（updating）

一、gcd lcm 基础中的基础，一般用来处理计算第一步什么的，分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题：
阅读更多...
Java 创建图形用户界面（GUI）入门指南（Swing库 JFrame 类）概述

Java 创建图形用户界面（GUI）入门指南（Swing库 JFrame 类）概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包，是 JAVA 基础类的一部分，基于 Java AWT 构建，提供了一系列轻量级、可定制的图形用户界面（GUI）组件。 与 AWT 相比，Swing 提供了许多比 AWT 更好的屏幕显示元素，更加灵活和可定制，具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多
阅读更多...
【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站，手机流量可以访问IPV6网络的服务，为什么不在电脑搭建Home Assistant（hass），来控制你的设备呢？@智能家居 @万物互联
阅读更多...
poj 2104 and hdu 2665 划分树模板入门题

poj 2104 and hdu 2665 划分树模板入门题

题意： 给一个数组n（1e5）个数，给一个范围（fr， to， k），求这个范围中第k大的数。 解析： 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码： poj 2104： #include <iostream>#include <cstdio>#include <cstdlib>#include <al
阅读更多...
MySQL-CRUD入门1

MySQL-CRUD入门1

文章目录 认识配置文件client节点mysql节点mysqld节点 数据的添加(Create)添加一行数据添加多行数据两种添加数据的效率对比 数据的查询(Retrieve)全列查询指定列查询查询中带有表达式关于字面量关于as重命名 临时表引入distinct去重order by 排序关于NULL 认识配置文件 在我们的MySQL服务安装好了之后, 会有一个配置文件, 也就
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2