搜索结果
查询Tags标签： 莫队，共有 28条记录-
莫队算法学习记录
什么是莫队：莫队是一种用于处理询问区间值的暴力离线算法，思路是通过移动两个指针到对应的区间来计算结果，精华是合理分块并依次处理。 什么时候用莫队：离线，暴力，1e5 原版莫队：建立区间（x1/2）:ll size=sqrt(n),bnum=ceil((double)n/size);for(ll i = 1; i <=…
2022/7/27 1:24:57 人评论 次浏览 -
莫队算法
普通莫队 对于询问奇偶分块 bool cmp(nd x,nd y) {int lb = x.x / bl,rb = y.x / bl;if (lb ^ rb) return x.x < y.x; // l,r同块以l排序return lb & 1 ? (x.y > y.y) : (x.y < y.y); //不同则看l在什么块内 } bool cmp(nd x,nd y){return (x.l / bl) ^ (y.…
2022/7/13 14:22:41 人评论 次浏览 -
莫队算法学习笔记
普通莫队"莫队算法"是用于一类离线区间询问问题的常用算法，以适用性广、代码量短、实际运行速度快、适合骗分等优点著称。 ——莫涛莫队的基本操作基于暴力实现，其降低复杂度的突破口在于处理“询问”。通过对询问合理的排序，使得之后的…
2022/3/31 22:49:25 人评论 次浏览 -
【NOI Online 2022】游记
提高组 上午 8 点左右就到了机房，等开始的时候划水…… 开题，先看 T1。CCF 的题目一般都很简洁，这次也不例外，很快明白了题意，但是没有很好的思路，就继续看题。 T2 很快有 \(O(n^3)\) 的想法，用 bitset 优化一下可以做到 \(O(n^2 \omega)\)，大概能拿 30~40 的样子…
2022/3/28 23:31:57 人评论 次浏览 -
【数据结构】【基础莫队】P1494 [国家集训队]小Z的袜子
目录【基础莫队】P1494 [国家集训队]小Z的袜子分析代码 【基础莫队】P1494 [国家集训队]小Z的袜子题意： 求区间[L,R]中抽到相同颜色的袜子的概率为多少？分析 设这段区间内各种不同颜色的袜子的数量依次为a,b,c,d,e,..... 所以答案为\(\sum_{i\in 袜子}\frac{i\times{(i-…
2022/2/11 6:15:10 人评论 次浏览 -
P5268 一个简单的询问（莫队+容斥）
目录Description State Input Output Solution CodeDescription 给你一个长度为 NNN 的序列 aia_iai，1≤i≤N1\leq i\leq N1≤i≤N，和 qqq 组询问，每组询问读入 l1,r1,l2,r2l_1,r_1,l_2,r_2l1,r1,l2,r2，需输出 ∑x=0∞get(l1,r1,x)get(l2,r2,x)\sum\limits_{x=0}^\inf…
2021/11/18 6:12:04 人评论 次浏览 -
P5268 一个简单的询问（莫队+容斥）
目录Description State Input Output Solution CodeDescription 给你一个长度为 NNN 的序列 aia_iai，1≤i≤N1\leq i\leq N1≤i≤N，和 qqq 组询问，每组询问读入 l1,r1,l2,r2l_1,r_1,l_2,r_2l1,r1,l2,r2，需输出 ∑x=0∞get(l1,r1,x)get(l2,r2,x)\sum\limits_{x=0}^\inf…
2021/11/18 6:12:04 人评论 次浏览 -
莫队算法浅析
莫队：著名 \(O(n\sqrt{n})\) 离线算法，思想基于分块。 做法 令 \(t = \sqrt{n}\) ，将区间左端点分成 \(t\) 块，按块从小到大排序，再将块内按从小到大排序。即： bool compare(node s1 , node s2){if(s1.x / t < s2.x / t) return true;if(s1.x / t > s2.x / t)…
2021/10/15 1:44:09 人评论 次浏览 -
莫队算法浅析
莫队：著名 \(O(n\sqrt{n})\) 离线算法，思想基于分块。 做法 令 \(t = \sqrt{n}\) ，将区间左端点分成 \(t\) 块，按块从小到大排序，再将块内按从小到大排序。即： bool compare(node s1 , node s2){if(s1.x / t < s2.x / t) return true;if(s1.x / t > s2.x / t)…
2021/10/15 1:44:09 人评论 次浏览 -
接下里一年的学习计划(2021.10~2022.10)
辗转反复，大概还是想打打acm的。 那就认真投入一次，看看能走多远吧。 2021.10 1.准备期中考试 2.Segment_Tree_Beats 3.线段树历史和 4.莫队，回滚莫队，二次离线莫队 5.dp 状态设计 斜率优化 决策单调性 6.计数 多项式 2022.11
2021/10/13 6:14:16 人评论 次浏览 -
接下里一年的学习计划(2021.10~2022.10)
辗转反复，大概还是想打打acm的。 那就认真投入一次，看看能走多远吧。 2021.10 1.准备期中考试 2.Segment_Tree_Beats 3.线段树历史和 4.莫队，回滚莫队，二次离线莫队 5.dp 状态设计 斜率优化 决策单调性 6.计数 多项式 2022.11
2021/10/13 6:14:16 人评论 次浏览 -
分治与根号算法
1. 根号分治与分块 1.1. 根号分治 根号分治，就是在预处理与询问的复杂度之间寻找平衡的一个算法。通常以根号作为问题规模的分界线，规模小于根号的询问可以 \(n\sqrt n\) 预处理求出，而回答一次规模为 \(B\geq n\) 的询问的时间只需要 \(\dfrac n B\leq \sqrt n\)，那么…
2021/10/4 1:40:47 人评论 次浏览 -
分治与根号算法
1. 根号分治与分块 1.1. 根号分治 根号分治，就是在预处理与询问的复杂度之间寻找平衡的一个算法。通常以根号作为问题规模的分界线，规模小于根号的询问可以 \(n\sqrt n\) 预处理求出，而回答一次规模为 \(B\geq n\) 的询问的时间只需要 \(\dfrac n B\leq \sqrt n\)，那么…
2021/10/4 1:40:47 人评论 次浏览 -
Count on a tree II （树上莫队）
题目链接 题意： 给定一棵\(N\)个节点的树，节点编号从\(1\)到\(N\)，每个节点都有一个整数权值。 现在，我们要进行\(M\)次询问，格式为\(u\) \(v\)，对于每个询问你需要回答从\(u\)到\(v\)的路径上（包括两端点）共有多少种不同的点权值。 思路： 树上莫队，预处理得到树…
2021/9/26 6:10:58 人评论 次浏览 -
Count on a tree II （树上莫队）
题目链接 题意： 给定一棵\(N\)个节点的树，节点编号从\(1\)到\(N\)，每个节点都有一个整数权值。 现在，我们要进行\(M\)次询问，格式为\(u\) \(v\)，对于每个询问你需要回答从\(u\)到\(v\)的路径上（包括两端点）共有多少种不同的点权值。 思路： 树上莫队，预处理得到树…
2021/9/26 6:10:58 人评论 次浏览
