分类 分块 下的文章

BZOJ 3781: 小B的询问

题目描述小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。输入第一行,三个整数N、M、K。第二行,N个整数,表示小B的序列。接下来的M行,每行两个整数L、R。输出M行,每行一个整数,其中第i行的整数表示第i个询问的答案。样例输入6 4 31 3 2 1 1 31 42 63 55 6样例输出6952提示对于全部的数据,1<=N、M、K<=50000题解裸的莫队算法,假设我们知道了区间 [l, - 阅读剩余部分 -

BZOJ 3343: 教主的魔法

题目描述教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。WD巨懒,于是他把这个回答的任务交给了你。输- 阅读剩余部分 -

【莫队】BZOJ 2038: [2009国家集训队]小Z的袜子(hose)

题目描述作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。输入输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。接下来一行包- 阅读剩余部分 -

BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊 LCT/分块

Description某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。Input第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依- 阅读剩余部分 -

BZOJ 2120: 数颜色

题目描述墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?输入第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。输出对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中- 阅读剩余部分 -

BZOJ 2453: 维护队列

题目描述你小时候玩过弹珠吗?小朋友A有一些弹珠,A喜欢把它们排成队列,从左到右编号为1到N。为了整个队列鲜艳美观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,A有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是A还没有学过编程,且觉得头脑风暴太浪费脑力了,所以向你来寻求帮助。输入输入文件第一行包含两个整数N和M。第二行N个整数,表示初始队列中弹珠的颜色。接下来M行,每行的形式为“Q L R”或“R x c”,“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中,一共有多少不同颜色的弹珠,“R x c”表示A把x位置上的弹珠换成了c颜色。输出对于每个Q操作- 阅读剩余部分 -

【分块】数列分块入门

前言我好弱啊,分块都不会,所以感觉学一下。分块基本做法一般将一个数列分成若干个块,如果只需要操作一个块中的部分数据,直接暴力修改,如果整个块都需要操作,对于整个块打一个标记而不进行实际的操作。调试技巧:可以生成一些大数据,然后用两份分块大小不同的代码来对拍,还可以根据运行时间尝试调整分块大小,减小常数。分块实例1 - 区间修改,单点求值给你一个长度为 n 的数列,有 n 个操作。一种是将 l 到 r 区间内所有的值都加上一个数 c。一种是求第 i 个点的值。代码#include <cstdio> #include <iostream> #includ- 阅读剩余部分 -