莫队算法 - hzwer.com

程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-67435dc5575fd971345778/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-67435dc55760c764229955/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-67435dc557614420858222/]POJ2373DividingthePath用dp(i)...
12017年6月24日8,635递推与动规,STL,快速幂,单调队列,莫队算法,高斯消元

「BZOJ3809」Gty的二逼妹子序列
DescriptionAutumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便，我们规定妹子们的美丽度全都在[1,n]中。给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。Input第一行包括两个整数n,m(1<=n<=100...
192014年12月21日18,271分块,莫队算法
「BZOJ3289」Mato的文件管理
DescriptionMato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...
42014年12月3日7,124树状数组,莫队算法
WC2013糖果公园
DescriptionInputOutputSampleInputSampleOutput841312784HINT题解30分暴力。。。模拟即可第4-5个测试点由于m较小，且在链上，所以可以用前缀和水过。。。对于每个询问统计每种糖果的答案贡献满分做法带修改树上莫队。。。参见vfk的博客http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080但是vfk的这种树分块方式。。。。。。感觉[B,3B]的话把应...
52014年11月29日9,026莫队算法,最近公共祖先
「BZOJ3757」苹果树
Description神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。有许许多多的...
02014年11月28日10,073莫队算法,最近公共祖先
「BZOJ3781」小B的询问
Description小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。Input第一行，三个整数N、M、K。第二行，N个整数，表示小B的序列。接下来的M行，每行两个整数L、R。OutputM行，每行一个整数，其中第i行的整数表示第i个询问的答案。SampleInput64313211314263556S...
12014年11月27日5,802莫队算法
「czy系列赛」czy的后宫3
czy的后宫3「题目描述」上次czy在机房妥善安排了他的后宫之后，他发现可以将他的妹子分为c种，他经常会考虑这样一个问题：在[l,r]的妹子中间，能挑选出多少不同类型的妹子呢？注意：由于czy非常丧尸，所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数，你懂得。问题简述:n个数，m次询问，每次问[l,r]区间有多少个数恰好出现正偶数次「输入格式」第一行3个整数，表示n,c,m第二行n个数，每个数Ai在[1,c]之间，表示一个Ai类型...
42014年7月19日10,094树状数组,离线处理,莫队算法
「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)
Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色...
212014年4月26日31,178莫队算法