首页 > 其他分享 >莫队 学习笔记

莫队 学习笔记

时间：2024-12-21 16:42:09浏览次数：7  
标签：cnt int 笔记 学习 read ans -- 莫队 define

阅前声明

题单
为方便，题目链接均在洛谷。

要用桶的时候请尽量不要使用 map 或者 un_map，会造成不必要的 TLE。

普通莫队

当一个区间问题，可以由 \([l,r]\) 转移到 \([l\pm 1,r]\) 和 \([l,r\pm 1]\)，且添加、删除都可以已很快的时间完成时，我们可以使用莫队算法。
我们先将询问离线下来，并将他们排序。我们先把数列分为若干个块，块长为 \(S\)，则先按 \(l\) 所在的区间排序，再按 \(r\) 的大小排序。
对于每一个询问，我们对于上个区间暴力转移到下个区间。可行转移方式之一是先扩大区间再缩小区间。
当 \(S=\sqrt{n}\) 时，时间复杂度为 \(n\sqrt{n}\)。

莫队的主体，按上面实现的话，应该是长这样：

int l=1,r=0;
For(i,1,m) {
	while(l>q[i].l) upd(a[--l]);
	while(r<q[i].r) upd(a[++r]);
	while(l<q[i].l) del(a[l++]);
	while(r>q[i].r) del(a[r--]);
	ans[q[i].idx]=sum;
}

DQUERY - D-query

题意：区间不同数

莫队主体是简单的，于是我们考虑加入和删除。
我们可以开一个桶保存每个数出现的次数：

  • 加入时如果保存该数的桶为空，那么答案加 \(1\)。
  • 删除后如果保存该数的桶为空，那么答案减 \(1\)。
  • 然后对桶进行操作即可。
点击查看代码 
#include<bits/stdc++.h>

#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,m,siz;
map<int,int> cnt;
int a[maxn];

struct node{
	int l,r,idx;
	bool operator<(const node &x) {
		return l/siz==x.l/siz?r<x.r:l<x.l;
	}
}q[maxn];

int sum=0;

void upd(int x) {
	if(cnt[x]==0) sum++;
	cnt[x]++;
}

void del(int x) {
	if(cnt[x]==1) sum--;
	cnt[x]--;
}

int ans[maxn];

void work() {
	in1(n);
	siz=sqrt(n);
	For(i,1,n) in1(a[i]);
	in1(m);
	For(i,1,m) in2(q[i].l,q[i].r),q[i].idx=i;
	sort(q+1,q+m+1);
	int l=q[1].l,r=q[1].l-1;
	For(i,1,m) {
		while(l>q[i].l) upd(a[--l]);
		while(r<q[i].r) upd(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].idx]=sum;
	}
	For(i,1,m) cout<<ans[i]<<'\n';
}

signed main() {
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

P1494 [国家集训队] 小 Z 的袜子

求区间 \([l,r]\) 中随机选出两个数相等的概率。

简单计数题。
用一个桶 \(cnt\) 保存每一个数出现的次数，考虑一个数 \(x\) 的贡献。

  • 加入 \(x\) 前，会对答案产生 \(cnt_x\) 的贡献。
  • 删除 \(x\) 后，会对答案造成 \(-cnt_x\) 的贡献。
点击查看代码 
#include<bits/stdc++.h>
#define int ll
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 50040
int n,m,siz;
int a[maxn],cnt[maxn];
struct quest{
	int l,r,idx;
}q[maxn];
bool cmp(quest a,quest b) {
	return a.l/siz==b.l/siz?a.r<b.r:a.l<b.l;
}
pair<int,int> ans[maxn];

int sum=0;
void upd(int x) {sum+=cnt[x]; cnt[x]++; }
void del(int x) {cnt[x]--; sum-=cnt[x]; }

void work() {
	in2(n,m);
	For(i,1,n) in1(a[i]);
	For(i,1,m) 
		in2(q[i].l,q[i].r),q[i].idx=i;
	siz=sqrt(n);
	sort(q+1,q+m+1,cmp);
	int l=q[1].l,r=q[1].l-1;
	For(i,1,m) {
		if(q[i].l==q[i].r) {
			ans[q[i].idx].first=0;
			ans[q[i].idx].second=1;
			continue ;
		}
		while(l>q[i].l) upd(a[--l]);
		while(r<q[i].r) upd(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].idx].first=sum;
		ans[q[i].idx].second=(r-l+1)*(r-l)/2;
		if(!ans[q[i].idx].first) ans[q[i].idx].second=1;
	}
	For(i,1,m) {
		int G=__gcd(ans[i].first,ans[i].second);
		cout<<ans[i].first/G<<'/'<<ans[i].second/G<<'\n';
	}
}

signed main() {
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

XOR and Favorite Number

询问 \([l,r]\) 中有多少个区间满足区间的异或和为 \(k\)。

首先我们知道 \(\oplus\) 是可以前缀和的。
然后求一段区间 \([l,r]\) 的异或和可以转换为前缀异或数组 \(s\) 的 \(s_{r}\oplus s_{l-1}\)。
所以答案变为求 \([l,r]\) 中 \(s_x \oplus s_y = k(x\le y)\) 的 \(\{x,y\}\) 对数。
我们用一个桶 \(cnt\) 来保存每个数的出现次数，那么：

  • 加入 \(x\) 前，会对答案产生 \(cnt_{x\oplus k}\) 的贡献。
  • 删除 \(x\) 后，会对答案产生 \(-cnt_{x\oplus k}\) 的贡献。
点击查看代码 
#include<bits/stdc++.h>
#define int ll
#define ll long long
#define i128 __int128
 
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
 
using namespace std;
 
int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
 
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
 
#define maxn 100050
 
int n,m,k,siz;
int a[maxn];
int cnt[maxn*20];
ll sum=0;
 
struct quest{
	int l,r,idx;
	bool operator<(const quest &x) const{
		return l/siz==(x.l/siz)?r<x.r:l<x.l;
	}
}q[maxn];
 
void upd(int x) {
	sum+=cnt[x^k];
	cnt[x]++;
}
 
void del(int x) {
	cnt[x]--;
	sum-=cnt[x^k];
}
int ans[maxn];
 
void work() {
	in3(n,m,k);
	siz=sqrt(n);
	For(i,1,n) in1(a[i]);
	For(i,1,n) a[i]^=a[i-1];
	For(i,1,m) {
		in2(q[i].l,q[i].r);
		q[i].l--;//前缀和导致的
		q[i].idx=i;
	}
	sort(q+1,q+m+1);
	int l=1,r=0;
	For(i,1,m) {
		while(l>q[i].l) upd(a[--l]);
		while(r<q[i].r) upd(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].idx]=sum;
	}
	For(i,1,m) cout<<ans[i]<<'\n';
}
 
signed main() {
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

P3709 大爷的字符串题

询问区间 \([l,r]\) 众数的出现次数。

我们用一个 \(cnt_x\) 记录 \(x\) 的出现次数，用一个 \(t_y\) 来表示出现次数 \(y\) 的个数。
那么我们有：

  • 每一次插入后，答案 \(ans\) 可以更新为 \(\max(ans,t_{cnt_x})\)；
  • 每一次删除前，如果答案为 \(cnt_x = ans\) 且 \(t_{cnt_x} = 1\)，那么 \(ans \to ans-1\)。（因为区间众数次数减一一定会有数，比如说这个 \(x\)）。
点击查看代码 
#include<bits/stdc++.h>

#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,m,siz;
int a[maxn],b[maxn];
struct node {
	int l,r,idx;
	bool operator<(const node &x) const {
		if(l/siz!=x.l/siz) return l<x.l;
		if((l/siz)&1) return r<x.r;
		return r>x.r;
	}
}q[maxn];
int cnt[maxn];
int t[maxn];

int mx;
int ans[maxn];

void upd(int x) {
	t[cnt[x]]--;
	t[++cnt[x]]++;
	mx=max(mx,cnt[x]);
}

void del(int x) {
	t[cnt[x]]--;
	if(cnt[x]==mx&&t[cnt[x]]==0) mx--;
	t[--cnt[x]]++;
}

void work() {
	in2(n,m);
	siz=sqrt(n);
	For(i,1,n) in1(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-b;
	For(i,1,n) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	For(i,1,m) {
		in2(q[i].l,q[i].r);
		q[i].idx=i;
	}
	sort(q+1,q+m+1);
	int l=1,r=0;
	For(i,1,m) {
//		cerr<<i<<" qwq\n";
		while(l>q[i].l) upd(a[--l]);
		while(r<q[i].r) upd(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].idx]=mx;
	}
	For(i,1,m) cout<<-ans[i]<<'\n';
}

signed main() {
//	freopen("P3709_2.in","r",stdin);
//	freopen("qwq.out","w",stdout);
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	int _=1;
//	_=read();
	For(i,1,_) {
		work();
	}
	return 0;
}

标签：cnt,int,笔记,学习,read,ans,--,莫队,define
From： https://www.cnblogs.com/CodingGoat/p/18620909

相关文章

  • 机器学习实验六：朴素贝叶斯算法实现与测试
    实验六：朴素贝叶斯算法实现与测试一、实验目的深入理解朴素贝叶斯的算法原理，能够使用Python语言实现朴素贝叶斯的训练与测试，并且使用五折交叉验证算法进行模型训练与评估。  二、实验内容（1）从scikit-learn库中加载iris数据集，使用留出法留出1/3的样本作为测试集（注......
  • 机器学习实验七：K 均值聚类算法实现与测试
    实验七：K均值聚类算法实现与测试一、实验目的深入理解K均值聚类算法的算法原理，进而理解无监督学习的意义，能够使用Python语言实现K均值聚类算法的训练与测试，并且使用五折交叉验证算法进行模型训练与评估。 二、实验内容（1）从scikit-learn库中加载iris数据集，使用留出法......
  • 机器学习实验八：随机森林算法实现与测试
    实验八：随机森林算法实现与测试一、实验目的深入理解随机森林的算法原理，进而理解集成学习的意义，能够使用Python语言实现随机森林算法的训练与测试，并且使用五折交叉验证算法进行模型训练与评估。 二、实验内容（1）从scikit-learn库中加载iris数据集，使用留出法留出1/3的......
  • 学期：2024-2025-1 学号：20241303 《计算机基础与程序设计》第十三周学习总结
    作业信息这个作业属于哪个课程<班级的链接>（如2024-2025-1-计算机基础与程序设计）这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第十三周作业)这个作业的目标<写上具体方面>加入云班课，参考本周学习资源；自学教材《C语言程序设计》第12章并完......
  • 学期2024-2025-1 学号20241424 《计算机基础与程序设计》第13周学习总结
    学期2024-2025-1学号20241424《计算机基础与程序设计》第13周学习总结作业信息|这个作业属于2024-2025-1-计算机基础与程序设计）||-- |-- ||这个作业要求在2024-2025-1计算机基础与程序设计第13周作业||这个作业的目标|<学习《C语言程序设计》第12章并完成云班课测试>||作......
  • 使用Anaconda和PyTorch编写深度学习Python代码
    摘要：通过Anaconda的虚拟环境和PyTorch的深度学习框架来建立Python的深度学习代码一、安装Anaconda在官网下载Anaconda，DownloadAnacondaDistribution|Anaconda等待漫长的下载过程这时候我推荐来一把酣畅淋漓的原神：二、配置Anaconda的国内镜像源参考：conda安装包_......
  • 图形学笔记 - 5. 光线追踪2 - 加速结构
    目录使用AABB加速光线追踪UniformSpatialPartitions(Grids)均匀空间划分空间划分KD树预处理KD-Tree数据结构遍历kd树对象划分&BoundingVolumeHierarchy层次包围盒BVHBVH遍历空间划分与物体划分呢GTCnews:DLSS、RTXGI实时光线追踪使用AABB加速光线追踪......
  • 机器学习实验一：数据准备与模型评估
    实验一：数据准备与模型评估一、实验目的 熟悉Python的基本操作，掌握对数据集的读写实现、对模型性能的评估实现的能力；加深对训练集、测试集、N折交叉验证、模型评估标准的理解。 二、实验内容（1）利用pandas库从本地读取iris数据集；（2）从scikit-learn库中直接加载ir......
  • 机器学习实验三：C4.5（带有预剪枝和后剪枝）算法实现与测试
    实验三：C4.5（带有预剪枝和后剪枝）算法实现与测试一、实验目的深入理解决策树、预剪枝和后剪枝的算法原理，能够使用Python语言实现带有预剪枝和后剪枝的决策树算法C4.5算法的训练与测试，并且使用五折交叉验证算法进行模型训练与评估。 二、实验内容（1）从scikit-learn库中加载......
  • JVM专题学习之类加载器（二）
    类加载器三层类加载器1.启动类加载器-BootstrapClassLoaderAppClassLoader负责加载核心类，存放在lib目录下的jar包或class文件。2.扩展类加载器-ExtensionClassLoaderExtensionClassLoader负责加载\lib\ext目录下的jar包或class文件，我们可以将通用性的功能，打成jar包放置到ext......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99