莫队专题
BZOJ 2038 小Z的袜子(hose) （莫队离线）
题目地址：BZOJ 2038 裸的莫队算法。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>#in
曼哈顿距离最小生成树与莫队算法
一、曼哈顿距离最小生成树 曼哈顿距离最小生成树问题可以简述如下： 给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。 朴素的算法可以用O(N2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O(N2)条，所以Kruskal的复杂度变成了O(N2logN)。 但是事实上，真正有用的边远没有O(N2)条。我们考虑每个点会和其他一些什
BZOJ2038 小Z的袜子（莫队算法）
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。 终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命。 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R的袜子中随机选出两只来穿。 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他
SP3267 DQUERY - D-query（莫队算法，区间不同数）
题意： 询问区间有多少个不同的数。 思路： 莫队裸题。 十分神奇的算法，我觉得关键就是离线排序，但是左端点的判据是第几块（分块），右端点的判据是大小。就这么一点点小改动，大大减小了复杂度ORZ。 #pragma GCC optimize(2)#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>us
2019CCPC湘潭邀请赛 Chika and Friendly Pairs（莫队+树状数组）
Problem Description Chika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of “friendly pairs” in a given interval. friendly pair: for two integers a
CodeForces 220B : Little Elephant and Array 莫队
传送门 题意 小象喜欢和数组玩。现在有一个数组 a a a，含有 n n n个正整数，记第 i i i个数为 a i a_i ai 现在有 m m m个询问，每个询问包含两个正整数 l j l_j lj和 r j ( 1 < = l j < = r j < = n ) r_j(1<=l_j<=r_j<=n) rj(1<=lj<=rj<=n)，小象想知道在 l l l到 r r r之
bzoj 2038: [2009国家集训队]小Z的袜子(莫队算法)
2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 15386 Solved: 6996 [Submit][Status][Discuss] Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜
CodeForces - 940F Machine Learning —— 带修改莫队
You come home and fell some unpleasant smell. Where is it coming from? You are given an array a. You have to answer the following queries: You are given two integers l and r. Let ci be the number of
CodeForces 617E XOR and Favorite Number（莫队）
题目链接：点击打开链接 题意：给n个数和一个k，有很多次查询，每次查询有l,r,求[l,r]有多少个子区间的xor之和等于k 思路：首先，亦或运算存在一个性质，即a^a=0，a^0=a,那么a^b=c,则a^b^b=a=b^c（两边同时亦或b）,区间[l,r]的区间亦或和为a[l]^a[l+1]^...^a[r]=a[1]^...^a[l-1]^a[1]^...^a[r]=sum[r]^sum
![洛谷P5072 [YNOI2015]盼君勿忘 莫队+unordered_set+毒瘤卡常](https://img-blog.csdnimg.cn/20190818201424260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9PSWVy,size_16,color_FFFFFF,t_70)
洛谷P5072 [YNOI2015]盼君勿忘 莫队+unordered_set+毒瘤卡常
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩 珂朵莉最可爱了，珂朵莉的题最毒瘤了qwq 题目链接：传送门 这是一个自带大常数选手被毒瘤 l x l lxl lxl卡常数，从开 O 2 O2 O2才 82
![[蓝桥杯 2023 省 A] 颜色平衡树：从零开始理解树上莫队 一颗颜色平衡树引发的惨案](https://img-blog.csdnimg.cn/direct/37bf18ff080647f6901ef90f608abf59.png)
[蓝桥杯 2023 省 A] 颜色平衡树：从零开始理解树上莫队 一颗颜色平衡树引发的惨案
十四是一名生物工程的学生，他已经7年没碰过信息学竞赛了，有一天他走在蓝桥上看见了一颗漂亮的颜色平衡树： [蓝桥杯 2023 省 A] 颜色平衡树 - 洛谷 十四想用暴力解决问题，他想枚举每个节点，每个节点代表一棵树，他想只要建立一个桶数组把每次出现的颜色放在桶里，每次遍历完一个节点和它的所有子节点后就统计这个桶数组
莫队入门(基础莫队，带修改的莫队，树上莫队..)
学习于胡小兔博客 自为风月马前卒博客 不带修改莫队： #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
SPOJ-DQUERY HYSBZ 1878 HH的项链 (线段树/树状数组/莫队/主席树)
1878: [SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MB Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一 段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一 个问题：某一段贝壳中，包含了多
1153 - 无影的神之右手(莫队算法)
1153 - 无影的神之右手 Time Limit：4s Memory Limit：512MByte Submissions：261Solved：31 DESCRIPTION 觉不觉得这几个图很有毒啊？ 其实这几个不算很有毒吧~ 由乃懒得写题面了，反正写了也没人看，所以直接说题意吧~ 给你一个序列a，每次查询一个区间[l,r]的乘积的约数个数mod 1926081
玲珑杯 1153 - 无影的神之右手 莫队
题目链接：http://www.ifrog.cc/acm/problem/1153 1153 - 无影的神之右手 Time Limit：4s Memory Limit：512MByte Submissions：183Solved：14 DESCRIPTION 觉不觉得这几个图很有毒啊？其实这几个不算很有毒吧~由乃懒得写题面了，反正写了也没人看，所以直接说题意吧~给你一个序列a，
#带修改莫队，分块#jzoj 1942 洛谷 1903 数颜色
题目 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 R P Col 把第P支画笔替换为颜色Col。需要满足查询 分析 这道题看起来就是要离线的，需要用莫队，但是原莫队不支持修改，那么就弄一弄，当然还要用分块优化，就没有什么了（jzoj卡逐字符输入） 代码 #include <cstdio>#include <cmath>#include <algor
HDU-4638-Group(莫队)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给你n个数字，m个要查询的区间。 查询的是l-r区间内有几段连续的数字。 样例解释： 1 - 5 有数字3 1 2 5 4.排一下序：1 2 3 4 5.连续。所以输出1。 2 - 4 有数字1 2 5 4.排一下序：1 2 4 5，1 2连续，4 5连续。所以输出2。 思路：
HDU-4467-Graph（莫队思想）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4467 题意：给你n个点，m条边，每条边有一个权值，有两个操作，一个是修改单点的颜色（颜色只有0,1两种），一个是询问边的两个端点都为指定颜色的权值和。 思路：由于每个点的颜色只有0，1两种，那么答案只有3种情况（00,01,11），用一个数组维护即可。即ans[0]统计边的两端都是0的权值和，an
Codeforces Round #340 (Div. 2)-E. XOR and Favorite Number(莫队)
题目链接：http://codeforces.com/contest/617/problem/E 题意：有n个数和m次询问，每一询问会有一个L和R，表示所询问的区间，问在这个区间中有多少个连续的子区间的亦或和等于k。 思路：首先说一下需要用到的异或的性质： 对于任何数x，都有x ^ x = 0。 对于任何数x，都有x ^ 0 = x。 那么我们预处理前缀异或和的结果，为什么这样做呢，比如给
P5268 [SNOI2017]一个简单的询问（莫队）
题目链接：https://www.luogu.org/problem/P5268 思路：对于只查询不修改，而且查询有关元素出现次数的要求，我们要用莫队做，但是莫队是用来处理一类双端点询问，所以我们要把式子拆成四个双端点询问。 题目中原式是这样的： ∑ x = 1 ∞ get ( l 1 , r 1 , x ) ∗ get ( l 2 , r 2 , x ) \large\sum\limits_{
黑龙江省赛 A Sequence Game(离散化+莫队算法+ST表 RMQ)
问题 D: A Sequence Game 时间限制: 1 Sec 内存限制: 128 MB 提交: 148 解决: 42 [提交] [状态] [讨论版] [命题人:admin] 题目描述 One day, WNJXYK found a very hard problem on an Online Judge. This problem is so hard that he had be
BZOJ2038小Z的袜子——莫队
Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他
Sona(莫队+离散化)
Sona, Maven of the Strings. Of cause, she can play the zither. Sona can’t speak but she can make fancy music. Her music can attack, heal, encourage and enchant. There’re an ancient score(乐谱). But be
SPOJ DQUERY - D-query （莫队算法）
Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in th