标签 - 树状数组

? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 树状数组 ? ? 树链剖分 ?    2019-01-05 11:01:15    706    0    0
【题目描述】风见幽香非常喜欢玩一个叫做 osu!的游戏,其中她最喜欢玩的模式就是接水果。 由于她已经DT FC 了The big black,  她觉得这个游戏太简单了,于是发明了一个更加难的版本。首先有一个地图,是一棵由 n 个顶点、n-1 条边组成的树(例如图 1给出的树包含 8 个顶点、7 条边)。这颗树上有 P 个盘子,每个盘子实际上是一条路径(例如图 1 中顶点 6 到顶点 8 的路径),并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树,所以从a_i到b_i的路径是唯一的),权值为c_i。接下来依次会有Q个水果掉下来,每个水果本质上也是一条
? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 树状数组 ?    2018-10-10 07:51:50    479    0    0
题目描述有一个长度为n的字符串,每一位只会是p或j。求一个最长子串,使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。(1≤n≤1 000 000) 输入输出样例输入样例#1: 复制6 jpjppj 输出样例#1: 复制4​​   遇到个数有关的问题首先把j看做-1,p看做1。这样就是要从左往右从右往左每个位置的前缀和都非负,处理原数组[前/后]缀和为pre[i]、suf[i]。 考虑对于位置i,先分别处理i向右最长能延伸到的地方和向左最长能延伸到的地方,记为R[i]和L[i]。这就相当于找到
? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 二分答案 ? ? 树状数组 ?    2018-01-25 16:48:15    549    0    0
DescriptionByteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby galaxy. The planet is unsuitable for colonisation due to strange meteor showers, which on the other hand make it an exceptionally interesting object of study. The member states of BIU have already placed s
? 解题记录 ? ? 洛谷 ? ? 树状数组 ? ? 差分 ? ? 模板 ?    2017-09-09 21:08:49    881    0    0
题目描述如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数数加上x 2.求出某一个数的和 输入输出格式输入格式:   第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含2或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k 操作2: 格式:2 x 含义:输出第x个数的值   输出格式:   输出包含若干行整数,即为所有操作2的结果。   输入输出样例输入样例#1:5 5
? 解题记录 ? ? 洛谷 ? ? 树状数组 ? ? 离散化 ?    2017-07-21 10:06:08    331    0    0
题目描述猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。 输入输出格式输入格式:   第一行,一个数n,表示序列中有n个数。 第二行n个数,表示给定的序列。   输出格式:   给定序列中逆序对的数目。   输入输出样例输入样例#1:6 5 4&nbs