树状数组 - Page 2

「BZOJ2738」矩阵乘法
Description　　给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。Input　　第一行两个数N,Q，表示矩阵大小和询问组数；接下来N行N列一共N*N个数，表示这个矩阵；再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。Output　　对于每组询问输出第K小的数。SampleInput2221341212111223SampleOutput13HINT　　矩阵中数...
02015年1月7日7,423二分法,树状数组

「BZOJ2527」[POI2011] Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日8,398二分法,树状数组
「codechefFNCS」Chef and Churu
题解分块水过将函数分块，每一块大小√n，预处理一块内的函数统计每一个数字的次数，以及这一块的答案这一部分n√n并用树状数组维护a的前缀和，线段树呵呵。。。对于询问将整块的答案加起来，其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数，更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优，但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...
12014年12月18日4,567分块,树状数组
「BZOJ3790」神奇项链
Description母亲节就要到了，小H准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小H购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或abaca。...
22014年12月11日6,567树状数组,manacher
「BZOJ2819」Nim
Description著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆...
82014年12月9日7,830dfs序,树状数组,博弈论
NOI2011阿狸的打字机
Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消...
32014年12月6日10,389dfs序,AC自动机,树状数组
「BZOJ3289」Mato的文件管理
DescriptionMato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...
42014年12月3日7,533树状数组,莫队算法
「BZOJ1145」[CTSC2008] 图腾totem
Description在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1,y...
12014年12月2日6,594树状数组
「BZOJ2789」letters
Description给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。Input第一行一个正整数n(2<=n<=1,000,000)，表示字符串的长度。第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。Output一个非负整数，表示最少的交换次数。SampleInput3ABCBCASampleOutput2HINTABC->...
02014年11月11日4,632树状数组
「NOIP模拟赛」弱点
「题目描述」一队勇士正在向你进攻，每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点，如果存在i<j<k使得ai>aj>ak，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。「输入」输入文件：weakness.in输入的第一行是一个整数n，表示勇士的数目。接下来一行包括n个整数，表示每个勇士的战斗值ai。「输出」输入文件：weakness.out输出为一行，包含一个整数。...
02014年11月4日3,323树状数组
「codecomb2097」rect
Description在一个n*m的格子棋盘上，有n*m堆石子，现在有两种操作：1、给(x1,y1)->(x2,y2)这个矩形内所有的石子堆加入k个石子。1<=x1<=x2<=n,1<=y1<=y2<=m。2、询问某格(x,y)上面有多少石子。Input第一行两个整数n和m，分别表示棋盘的长宽，n对应上述的x轴，m对应y轴。第二行一个整数p，表示操作数量。以下p行，首先一个是整数t，t=1或2，表示是哪种操作。如果t=1，则后面跟5个整数x1,y1,x2,y2,k，如上所...
02014年10月16日2,944树状数组
「BZOJ1106」[POI2007] 立方体大作战tet
Description一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除...
02014年10月11日3,617树状数组