线段树&树状数组
关注
分享
扫一扫
Deep_Kevin
这个作者很懒，什么都没留下…
展开
-
[SDOI2009]虔诚的墓主人，洛谷之提高历练地，其他数学问题
正题 第四题：[SDOI2009]虔诚的墓主人 这个东西，根据题意我们可以知道当前点的虔诚度为C(up,k)*C(down,k)*C(left,k)*C(right,k); 这里的四个英文单词，分别表示上面的常青树个数，下面的常青树个数，左边的常青树个数和右边的。 我们现在要做的事情就是如何维护这四个值。 对于30分做法，很明显就是用四个数组来存储...原创 2018-04-09 14:15:18 · 365 阅读 · 3 评论 -
睡觉困难综合征，洛谷P3613，树链剖分+树上较复杂合并
正题 一看到这题就心碎emm，好好睡觉不行吗。。。 关键看完这道题，你就要想到，用树链剖分+线段树来维护，因为在这方面线段树是最灵活而且是最万能的。我们就要想，怎么去进行线段树合并。 首先，您不可能建2^64个线段树。然后第i个线段树维护i经过这个线段树的某个区间所留下来的值。 这样的时间复杂的虽然比起暴力来好像快很多，但是细想还是不行。 想着拆位...原创 2018-06-13 20:26:44 · 301 阅读 · 0 评论 -
NOIP模拟赛，礼物，线段树优化建图
正题 题目是这样的： Rose一共有n个礼物，他女朋友也有n个礼物。 这些礼物有两个权值，x表示的是该礼物在Rose眼里的重要度，y表示的是该礼物在其女朋友眼里的重要度。 当一个人收到自己眼里价值为的礼物时，会回赠在自己眼里在的礼物。 当一个人收到自己眼里价值为0的礼物时，会觉得对方没有诚意，所以就会停止送礼物。 ...原创 2018-11-08 21:11:20 · 275 阅读 · 0 评论 -
[HAOI2012]道路，洛谷P2505，最短路图
正题 这题还是挺好想的。 把每个点作为起点的最短路图建出来。 做一次拓扑排序，求起点到该点有多少条最短路图。 然后做一次反拓扑序，求出该点可以到达其他点的路径种数。 最后对于边，它的价值就是u的第一个价值乘上v的第二个价值。 相当于算的是以i为起点的最短路有多少条经过这条边。答案全部加起来就可以了。#incl...原创 2018-11-08 20:31:56 · 444 阅读 · 0 评论 -
首师大附中集训第八天综合测试
综合测试 第一题：给出一个长度为 N 的序列 A[n]和 M 个操作，操作分为两种类型： 类型一，给出参数 l r k b 对于 l 到 r 之间(闭区间)的所有数 i ,令 A[i] = max(A[i],k*(i-l)+b ) 类型二，给出参数 l r, 求出 A[l] 到 A[r] 共(r-l+1)个数之中的最大值。 我们用线段树维护，每一个节点维护当前的直线，如...原创 2019-07-29 18:27:59 · 250 阅读 · 0 评论 -
陌上花开，Luogu P3810，cdq分治
正题 我也太菜了，最近才把这道题做了。 具体就是三维偏序，可以直接排序消掉一维，然后用cdq分治消掉一维，最后用树状数组消掉最后一维。 具体的细节就是abc都相等的时候要考虑虽然前面对后面的影响可以算出来，但是后面对前面的影响是不会算到的，一开始从后往前过一遍就可以了。 如何cdq套cdq还要再学一学，回来再补。#include<...原创 2019-07-24 21:01:04 · 201 阅读 · 0 评论 -
首师大附中集训第七天综合模测
综合模测 第一题：Alice和Bob是好朋友，她们经常喜欢在一起玩石子游戏。这一次他们想出了一个新 玩法：有若干堆石子，要求每次在一堆数量不为1的石子堆中取出石子，假设这堆石子 的个数是x，那么允许取的个数为正整数d，要求d|x且d ≠ x。如果没有办法再取石子了， 需要操作的那一方就输了。 游戏初始有m堆石子，每堆石子的个数均为1到n之间的正整数。Alice和Bob都是绝 对聪明的...原创 2019-07-29 20:34:54 · 714 阅读 · 0 评论 -
首师大附中集训第十一天综合测试
正题 第一题：Door Street 是一条繁华的街道，沿街一共有栋大楼，编号依次为 ，相邻两栋楼编号相邻。 现在你想在 Door Street 开一家咖啡厅，你可选址在任意一栋楼内。每栋楼都有一个消费指数 。若你 选址在第x号楼，则第i号楼的人在你的咖啡厅消费 ，你的收入是 n 栋大楼的 人的消费总和，即 。 对于每栋大楼，你想评估出你若选址在该大楼，你的收入分别是多少？ ...原创 2019-08-01 19:22:33 · 299 阅读 · 0 评论 -
首师大附中集训第十七天综合模测
正题 第一题：区间和2 给出一个序列A，把所有子区间的和提出来后排序，询问的和。 首先考虑差分，然后二分那个值是多少，check用Two_Pointers，直接用一个二分前缀和计算答案即可。 #include<cstdio>#include<cstdlib>#include<cstring>#i...原创 2019-08-08 20:34:16 · 277 阅读 · 0 评论 -
首师大附中集训第十八天综合模测
正题 今天写线段树和树状数组写得很爽 第一题：括号匹配 也许就我的做法这么傻，考虑将左括号看成1，右括号看成-1，然后目的就是交换两个不同的括号，使得所有的前缀和>=0。 每次贪心取第一个右括号和最后一个左括号交换即可，这个过程用set维护，用线段树维护前缀和。 题解非常简单。#include<set>...原创 2019-08-09 18:25:12 · 234 阅读 · 0 评论 -
[JLOI2014]松鼠的新家，洛谷P3258，树链剖分
正题 这题十分的简单，就是修改树上的多条路径（每个位置加一），然后输出。 动态修改就可以想到树链剖分，所以我们用树链剖分维护一下就可以了。很水不多说#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;...原创 2018-06-13 20:00:40 · 260 阅读 · 0 评论 -
[SDOI2011]染色，洛谷P2486，树链剖分+较复杂的线段树维护
正题 快来树上涂颜色吧！ 其实就是普通的树链剖分+较复杂的线段树维护。 求一段颜色有多少个分块用线段树维护到底应该怎么求。 我们一棵线段子树应该怎么从左儿子和右儿子的关系推出来？ 当然很简单，每一棵线段子树可以记录下最左节点的颜色和最右节点的颜色。 那么当且仅当左边的最右节点和右边的最左节点相同，一个区间才会被计算两次。 所以，...原创 2018-05-29 13:13:08 · 425 阅读 · 0 评论 -
树状数组（改点求段） ，洛谷之提高历练地，提高模板-nlogn数据结构
正文 这题知道树状数组的肯定秒打咯~ 我们首先要清楚lowbit(x)这个数组的含义，指的是，x最后的一个1及其后面的0组成的二进制数。如lowbit(1001001101100(2))=100(2)=4lowbit(1010101101010000(2))=10000(2)=16; 所以我们可以肯定的是lowbit一定是一个2的幂次方数。 在树状数组里面表示...原创 2018-04-17 10:15:47 · 238 阅读 · 0 评论 -
树状数组（改段求点） ，洛谷之提高历练地，提高模板-nlogn数据结构
正题 该段求点看似很难，如果我们可以一次性把i到n都加上某个数就好了~~ 不难想到用差分的思想，我们每次处理一下当前这个数与前面一个数的差值，那么通过统计这个数组的前缀和就可以完成我们的操作。 比如说我们用一个diff[i]来表示i与i-1的差值，那么p[i]=sigma(diff[j])(j=[1~n]);想想是不是。 那么sigma这个操作我们用树状数组...原创 2018-04-17 10:30:30 · 228 阅读 · 0 评论 -
线段树（该段求段+lazy）优化，洛谷之提高历练地，提高模板-nlogn数据结构
正文 这个东西挺简单的吧，线段树就不细讲了，主要讲讲lazy。 懒嘛~ 如果当前覆盖整个区间，那么我们就用lazy把它那个值记录下来，然后，如果不是完全覆盖当前区间，那么我们就把它下放，乘的话那你就用一下乘法分配律搞一下即可#include<cstdio>#include<cstdlib>#include<cstring>i...原创 2018-04-17 10:47:46 · 200 阅读 · 0 评论 -
[AHOI2009]维护序列，洛谷之提高历练地，线段树树状数组基础
正题 第三题：[AHOI2009]维护序列 这道题是线段树的模板，只要用lazy记录一下即可，注意处理两个lazy（加和乘）的时候，注意运用乘法分配律。#include<cstdio>#include<cstdlib>#include<cstring>#define LL long longint n,m;LL mod;stru...原创 2018-04-19 09:12:01 · 247 阅读 · 0 评论 -
[JSOI2008]最大数，洛谷之提高历练地，线段树树状数组基础
正题 第一题：[JSOI2008]最大数 这道题是可以用倍增维护最大值来做，每次加入一个点，维护一遍倍增数组（ST表）logn复杂度。 我也没拦着你用线段树加点。。。#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include&...原创 2018-04-19 09:23:50 · 222 阅读 · 0 评论 -
瓜瓜的时空旅行，第三次模拟赛，dfs序+线段树维护最小值
题目描述 西瓜们生活在编号 1⋯n 的 n个平行时空中，2n−2 台时光机将这些平行时空联系在一起。一台时光机有 3个整数参数 u,v,t 表示从时空 u 可以花费 t 的时间穿梭到时空 v。为了确保时空之间可以相互穿梭，同时方便作为现世的 1号时空的通行，西瓜们将这些时光机进行分工：前 n−1 台.时光机确保从 1号时空可以直接 / 间接抵达任意时空，后 n−1台时光机负责从 2⋯n...原创 2018-04-24 08:14:00 · 310 阅读 · 0 评论 -
借教室，洛谷之提高历练地，暴力？？差分
正题 借教室 我们每加入一个区间，就将这个区间都加上dj，没错，我们只要看一下当前点的权值是否大于ri即可。 lazy优化+读入优化强行卡过// luogu-judger-enable-o2#include<cstdio>#include<cstdlib>#include<cstring>#include<iostre...原创 2018-04-24 10:15:58 · 250 阅读 · 0 评论 -
Dynamic Rankings，洛谷P2617，树状数组+主席树
正题 这道题我理解了半天，网上好的题解我没有看懂，所以在这里尽量写得详细简略一些。 动态第k大要了解的是两个东西。 一个是树状数组的概念，一个是主席树（动态开点线段树）。 先讲树状数组; 1.定义一个点i维护的信息是[i-lowbit(i)+1,i].lowbit()这个函数的意义是i在二进制下末尾零和倒数第一个数组成的数。像lowbit(7) = l...原创 2018-05-22 18:23:53 · 367 阅读 · 0 评论 -
[CQOI2011]动态逆序对，洛谷P3157，树状数组+主席树
正题 大家可能看到这题就觉得无从入手。 但是我们可以从逆序对的定义入手，每个点可以计算出前面有多少个比他大的，后面有多少个比他小的。 第一次输出的答案就是这两个其中之一的总和。 那么每删去一个点，就相当于把前面比他大的点和后面比他小的点的总和去掉。 又发现每次删除可能会与前面删去的某些点组成逆序对（删两次）。 所以转化问题为，每次加入一个...原创 2018-05-22 18:40:16 · 385 阅读 · 0 评论 -
首师大附中集训第十九天综合模测
正题 第一题：. 红树和蓝树 有n个节点的树，节点从1到n标号， n-1条边中的第i条边连接节点ai和bi。 开始的时候所有的边都是蓝色，Takahashi会通过n-1步操作把这个蓝色的树变成红色。 每次操作包含以下步骤： 1.选择一个只包含蓝色的简单路径，然后移除上面的一条边。 2.在选出的蓝色简单路径的两个端点之间加一条红边。 他想把树变恰好变成一棵每条边连接ci...原创 2019-08-10 18:53:06 · 278 阅读 · 0 评论