RainAir
My OI Blog
RainAir

线段树
文章归档

JZOJ 2019.11.02 总结

赛时 T1 一看暴力分是之前做过的原题,所以就粘写完了 $O(n^2logn)$ 的暴力, T2 想了想,发现每次一定要把最小值移动到左边或右边,然后可以递归成子问题去做了 T3 建出来树之后只会暴力 dp。 最后 40+100+25 第三题挂了 20 分完美省三。 题解 A. Game $O(n^2logn…

   77   2019-11-03   77 去吊打作者

「CF833B」The Bakery

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

   232   2019-08-26   232 去吊打作者

「ZROI849」 大厦

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

   215   2019-07-17   215 去吊打作者

DDP 学习笔记

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

   274   2019-07-11   274 去吊打作者

「BZOJ5028」小Z的加油店

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

   494   2018-11-24   494 去吊打作者

GSS 系列题目题解

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

   440   2018-10-11   440 去吊打作者

[HEOI2016/TJOI2016]排序

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

   466   2018-10-11   466 去吊打作者

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$。 解题报告 这个有和,我们可以用线段树维护。 线段…

   462   2018-10-02   462 去吊打作者

「NOIP2017」列队

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

   332   2018-07-17   332 去吊打作者

线段树模板

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

   589   2017-12-03   589 去吊打作者
标签
近期评论