RainAir
My OI Blog
RainAir

线段树
文章归档

「CF833B」The Bakery

题目大意 把 $n$ 个数分成 $k$ 个区间,每个区间的价值为区间内不同数字的个数,问价值和最大为多少。 题解 简单 dp:设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量,那么有转移 $$f_{i,j} = …

   152   2019-08-26 去围观

「ZROI849」 大厦

题目描述:给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线,这些直线与坐标轴的夹角是 45 度,问在矩形 $(0,0) \to (W,H)$ 中,有多少个子矩形。 图片示意: 上图有 $19$ 个子矩形。 $n \leq 10^5$ 首先这一题目 $O(n^3)$ 的复杂度十分好做:就是枚举三条边 去 map 找一下…

   141   2019-07-17 去围观

DDP 学习笔记

DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡,现在回来学一学。 我们来找一…

   167   2019-07-11 去围观

「BZOJ5028」小Z的加油店

题目描述 题目链接 小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有三种操作: 1. 把一个瓶子完全加满; 2. 把一个瓶子完全倒空; 3. 把一个瓶子里…

   419   2018-11-24 去围观

GSS 系列题目题解

记录一下本人目前会做的 GSS 系列题目。 目前已经完成 GSS1,GSS3,GSS4,GSS5。 GSS1 题目描述 求最大子段和,序列的值可能为负数。 其中长度 $\leq 50000$。 解题报告 线段树维护这个序列。 线段树中维护四个值:$sum,lans,rans,ans$,分别表示当前序列的和,…

   388   2018-10-11 去围观

[HEOI2016/TJOI2016]排序

题目描述 题目链接 对一个长度为 $n$ 的排列进行 $m$ 次如下操作: 将区间 $[l,r]$ 中的数字升序排序。 将区间 $[l,r]$ 中的数字降序排序 最后输出位置 $p$ 的数字。 其中 $1 \leq n,m \leq 10^5$ 解题报告 发现询问只有一组,我们可以考虑二分答案。 考…

   408   2018-10-11 去围观

Can you answer these queries III

题目描述 题目链接 给定一个长度为 $n$ 的序列 $a$,有 $q$ 个询问,询问有两种: 单点修改 给定一组 $L,R$,求 $$max{\Sigma_{i=l}^{r}a_i}(L\leq l \leq r \leq R)$$ 其中 $n,q \leq 50000$。 解题报告 这个有和,我们可以用线段树维护。 线段…

   404   2018-10-02 去围观

「NOIP2017」列队

题目链接 解题报告 我们对于每行建一棵线段树维护人,对于最后一列建一棵线段树。 我们要实现能插入删除的线段树,预先开点即可。 但是这样空间会爆,我们需要动态开点。 详情见代码。 [crayon-5d82877825861387260833/]

   268   2018-07-17 去围观

线段树模板

一种快速的区间查找算法 线段树和树状数组一样,都可以在$ n log_2 n $ 的时间复杂度下求出一个动态区间的最优值。 模板一 模板二 定义 线段树是一种树形结构(这不是废话吗),它的每个结点存储的是一条线段。它是一个能在$ O(logn) $ 的时间复杂度中进行区间修…

   527   2017-12-03 去围观
标签
近期评论