莫队-小Z的袜子
----普通莫队首先清楚概率怎么求假设我们要求从区间l到r中拿出一对袜子的概率sum[i]为第i种袜子在l到r中的数量$$\frac{\sum_{i=l}^{r} {[sum[i] \times (sum[i]-1)]}}{ (r-l+1) \times {(r-l)}}\qquad$$转化一下可以...
【莫队算法】【权值分块】bzoj3920 Yuuna的礼物
【算法一】暴力。可以通过第0、1号测试点。预计得分：20分。【算法二】经典问题：区间众数，数据范围也不是很大，因此我们可以：①分块，离散化，预处理出：<1>前i块中x出现的次数(差分)；<2>第i块到第j块中的众数是谁，出现了多少次。询问的时候，对于整块的部分直接获得答案；对...
Codeforces 86D Powerful array(莫队算法)
莫队算法的裸题。n^2可以展开成等差数列1+3+5....+2*n-1的和，这样一来插入和删除操作就变得简单多了。 #include<cstdio>#include<cmath>#include<algorithm>#define MAXN 200010usin...
whu oj 1551 Pairs （莫队算法）
problem_id=1551">题目链接题目大意：给出的询问，求出这个区间的里 差小于等于 2 的数字的对数。思路分析：莫队算法。然后分析一下。假设添加了一个数字。那么就要加它旁边相差为2 的数字的和。反之降低一个。就要降低相差为2 的数字的和。再减去自己这个1.。#include <...
【分块】【树上莫队】bzoj1086 bzoj3052
1086http://vfleaking.blog.163.com/blog/static/174807634201231684436977/3052http://vfleaking.blog.163.com/blog/static/174807634201311011201627/1086 看了一...
莫队算法
莫队算法可以一个可高效解决绝大多数离线+无修改+区间查询问题的算法。这类问题具体是指：如果知道[L,R]的答案时，可以在O(g(n))的时间下得到[L,R−1],[L,R+1],[L−1,R],[L+1,R]的答案的话，就可以在的时间内求出所有查询。假设我们算完[L,R]的答案后现在要算[L′,R′...
[Bzoj2120]数颜色 （非正解 ）（莫队）
2120: 数颜色Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 6286 Solved: 2489[Submit][Status][Discuss]Description墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提...
BZOJ2120 数颜色 —— 待修改莫队
题目链接：https://vjudge.net/problem/HYSBZ-21202120: 数颜色Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 6898 Solved: 2781[Submit][Status][Discuss]Descripti...
BZOJ2120 数颜色（带修改莫队）
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！Description墨墨购买了一套N支彩色画笔（其中有些颜色...
Codeforces 86D - Powerful array(莫队算法)
题目链接：http://codeforces.com/problemset/problem/86/D 题目大意：给定一个数组，每次询问一个区间[l,r]，设cnt[i]为数字i在该区间内的出现次数，求该区间内所有的cnt[i]^2*i。 解题思路：莫队模板题，改一下add,remove就好了。 ...
codeforces 86D Powerful array 莫队算法
题意： 给你n个数字，m个区间，要你算出每个区间内si*Ksi*ksi总和。 题解： 莫队算法模板题，每移动一次的时候减去之前的影响再加上现在的影响就可以了，具体看代码。 #include<stdio.h> #include<string.h>#include&l...
数据结构（莫队算法）：国家集训队2010 小Z的袜子
【题目描述】作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，...
【BZOJ-3052】糖果公园 树上带修莫队算法
3052: [wc2013]糖果公园Time Limit: 200 Sec Memory Limit: 512 MBSubmit: 883 Solved: 419[Submit][Status][Discuss]DescriptionInputOutputSample InputSample O...
树上莫队 wowow
构建：像线性的莫队那样，依旧是按sqrt(n)为一块分块。 int dfs(int x){ int size=; dfn[x]=++ind; for (int i=;i<=;i++) if (bin[i]<=deep[x]) fa[x][i]=...
CodeForces - 220B Little Elephant and Array (莫队+离散化 / 离线树状数组）
题意：N个数，M个查询，求[Li,Ri]区间内出现次数等于其数值大小的数的个数。分析：用莫队处理离线问题是一种解决方案。但ai的范围可达到1e9，所以需要离散化预处理。每次区间向外扩的更新的过程中，检查该位置的数ai的出现次数是否已经达到ai或ai+1，以判断是否要更新结果。同理，区间收缩的时候判断...
BZOJ3236[Ahoi2013]作业——莫队+树状数组/莫队+分块
题目描述输入输出样例输入3 41 2 21 2 1 31 2 1 11 3 1 32 3 2 3样例输出2 21 13 22 1提示N=100000,M=1000000莫队+树状数组：先考虑每次询问没有权值区间限制的情况，将询问离线排序，用一个数组记录答案，莫队即可。但现在每次询问有了查询的权值区间...
算法复习——莫队算法（bzoj1878）
题目：DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。...
BZOJ 2038: [2009国家集训队]小Z的袜子(hose) [莫队算法]【学习笔记】
2038: [2009国家集训队]小Z的袜子(hose)Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 7687 Solved: 3516[Submit][Status][Discuss]Description作为一个生活散漫的人，小Z每天早上都要耗...
BZOJ2120 数颜色 【带修莫队】
BZOJ2120 数颜色Description墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。 为了满...
bzoj2120 数颜色 莫队 带修改
【bzoj2120】数颜色Description墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨...