【 Gym - 101138D 】Strange Queries （莫队算法）
BUPT2017 wintertraining(15) #4BGym - 101138D题意a数组大小为n。(1 ≤ n ≤ 50 000) (1 ≤ q ≤ 50 000)(1 ≤ ai ≤ n)q个查询，询问两个区间相同的数有多少对。题解[sl,sr]和[tl,tr]区间相同的数的对数可以用\(...
BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块
BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块Description有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r...
luoguP4466 [国际集训队]和与积 莫比乌斯反演
自然想到枚举\(gcd(a, b)\)，不妨设其为\(d\)，并且\(a = di, b = dj(a > b)\)那么\(\frac{ab}{a + b} = \frac{dij}{i + j}\)由于此时有\((i,j) = 1\)，因此\((i, i + j) = (j, i + j) ...
2018.11.07 NOIP训练 L的鞋子（权值分块+莫队）
传送门乱搞题。我直接对权值分块+莫队水过了。不过调了30min30min30min发现ststst表挂了是真的不想说什么233.代码
2019.01.08 bzoj3809: Gty的二逼妹子序列（莫队+权值分块）
传送门题意：多组询问，问区间[l,r]中权值在[a,b]间的数的种类数。看了一眼大家应该都知道要莫队了吧。然后很容易想到用树状数组优化修改和查询做到O(mnlogamax)O(m\sqrt nlog_{a_{max}})O(mnlogamax)的时间复杂度。然后发现可以上一波权值分块，这样的话...
HDOJ 5381 The sum of gcd 莫队算法
大神题解:http://blog.csdn.net/u014800748/article/details/47680899The sum of gcdTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java...
HDU 4676 Sum Of Gcd 【莫队 + 欧拉】
任意门：http://acm.hdu.edu.cn/showproblem.php?pid=4676Sum Of GcdTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total ...
[CSP-S模拟测试]:sum（数学+莫队）
题目传送门（内部题63）输入格式第一行有一个整数$id$，表示测试点编号。第一行有一个整数$q$，表示询问组数。然后有$q$行，每行有两个整数$n_i,m_i$。输出格式一共有$q$行，每行一个整数表示每组询问的答案$S_{n_i,m_i}$对$10^9+7$取模的结果。样例样例输入：151 12 ...
bzoj3920: Yuuna的礼物（莫队+分块套分块）
思路挺简单的，但是总感觉好难写...码力还是差劲，最后写出来也挺丑的这题显然是个莫队题，考虑怎么转移和询问...根据莫队修改多查询少的特点，一般用修改快查询慢的分块来维护。查第$k_1$小的出现次数可以用权值分块做到$O(1)$修改，$O(\sqrt{n})$查询，$k_2$小的数同理。对于每一种出...
hdu 5381 The sum of gcd 2015多校联合训练赛#8莫队算法
The sum of gcdTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 23 Accepted Submission(s): 4P...
[SNOI2017]一个简单的询问【莫队+容斥原理】
题目大意给你一个数列，让你求两个区间内各个数出现次数的乘积的和。分析数据范围告诉我们可以用莫队过。我并不知道什么曼哈顿什么乱七八糟的东西，但是我们可以用容斥原理将这个式子展开来。\[\sum^{\infty}_{0}get(l_1,r_1,x)\times get(l_2,r2,x)\]上述式子是题...
【BZOJ2038】【2009国家集训队】小Z的袜子(hose) 分块+莫队
Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否...
bzoj 3236: 洛谷 P4396: [AHOI2013]作业 (莫队, 分块)
题目传送门：洛谷P4396。 题意简述： 给定一个长度为\(n\)的数列。有\(m\)次询问，每次询问区间\([l,r]\)中数值在\([a,b]\)之间的数的个数，和数值在\([a,b]\)之间的不同的数的个数。 题解： 第一问可以用主席树维护，但是第二问呢？ 考虑离线处理询问，用莫队算法。 问题...
hdu 4358 Boring counting dfs序+莫队+离散化
Boring countingTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)Problem DescriptionIn this problem we consider a roo...
【洛谷】1972：[SDOI2009]HH的项链【莫队+树状数组】
P1972 [SDOI2009]HH的项链题目背景无题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了...
洛谷 P3674 小清新人渣的本愿 [莫队 bitset]
传送门题意：给你一个序列a，长度为n，有Q次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1,2,3题面太强啦！！！感觉就是莫队，想了一下分块不好搞更坚定了莫队的信念$a-...
【Luogu4396】[AHOI2013]作业（莫队）
【Luogu4396】[AHOI2013]作业（莫队）题面洛谷题解模板题#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define MAX 300300inlin...
bzoj 3809 莫队
收获：1、分块时顺便记录每个位置所属的块，然后一次排序就OK了。2、要权衡在“区间移动”与“查询结果”之间的时间，莫队算法一般区间移动频率远大于查询结果，所以我们选择的辅助数据结构时就要注意了，我最开始写的是值域线段树，自己生成的极限数据要1m8s，改成树状数组后要24s，还是过不了，hzwer只要...
bzoj 2038 小z的袜子 莫队
莫队大法好，入坑保平安只要能O(1)或O(log)转移，离线莫队貌似真的无敌。#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath...
Little Elephant and Array CodeForces - 220B（莫队）
给一段长为n的序列和m个关于区间的询问，求出每个询问的区间中有多少种数字是 该种数字出现的次数等于该数字 的。#include <iostream>#include <cstdio>#include <sstream>#include <cstring>...