Phecda_

分类

未归档(109)

/ 注册

全部文章（共12篇）

线段树【注意事项】

乘标记由于乘法分配律的存在，直接乘就好了但是，加标记，一定要记得乘上节点所管辖的区间长度！！！一定要记得乘上节点所管辖的区间长度！！！一定要记得乘上节点所管辖的区间长度！！！（重要的事情说三遍）就这些了...

线段树

2018-05-27

0 349

LuoGu P1083 借教室

题目传送门借教室这个题有两种做法，差分+前缀和或者是线段树线段树维护区间最小值，因为能不能借教室使用是由这几天中可用教室最少的一天决定的其实这题是个很裸的线段树维护区间最小值，但有一点需要注意，区间最小值在进行加减修改时不能乘以区间长度很简单，不论区间长度怎么样，你整个区间-x，最小...

二分答案线段树差分前缀和

2018-09-06

0 468

清北学堂清北-Day3-R2-打架 (fight)

题目描述 LYK有 \(n\) 个小朋友排成一排。第 \(i\) 个小朋友的战斗力是 $ a_i $，且他们的战斗力互不相同。战斗力高的会打败战斗力低的。 LYK想恶搞这些小朋友们，具体地，它有 \(k\) 次操作。第i次操作会有两个参数 \(l_i\) 和 \(r_i\) ，表示如果两个...

线段树

2018-11-01

0 415

RDay2-Problem 2 B

题目描述小明家有n个信箱，前前后后来送信和取信的总次数为q，称为q次访问，其中这q次访问分成三种类型。 1：邮递员送来了一封信，放在了x号信箱。 2：小明取走了x号信箱的所有信（x信箱可能已经没有信了）。 3：小明取走了前t封送来的信（前t封表示从送来的第一封到送来的第t封，其中这t封信可能已经通...

线段树链表

2018-11-05

0 433

USACO15DEC最大流MaxFlow

传送门这是个假的最大流,其实是一个用树剖+线段树就能解决的事情题目中的道路会对路径上的造成压力,最后询问最大的压力其实就等价于对每条路径上的点加上 1 的权值,并且最后询问整个树中的最大值然后树剖+最大值线段树裸题,完事,莫得别的问题了. \(Updated:\) 其实,可以树上差...

树链剖分线段树差分

2019-04-28

0 486

浅谈线段树

线段树一种初级数据结构(之前一度是高级),相信大多数学习数据结构的人都能熟练地掌握它. 线段树最初开发的意义是高效率地作用于区间操作(对数据的维护),但这个所谓的高效率也并不很高.但,相对于目前已经开发出来的一般性数据结构,线段树无疑是非常优秀且稳定的一个. \(\Theta ( n \times ...

线段树

2019-05-05

0 325

CodeForces1208D

CodeForces1208D 也是挺吓人的一道题,我一开始以为给的是每个数字前比它小的数字有几个,然后我就苦苦看不懂样例... 然后我冷静了一下,重新分析,读题,发现给的是每个数字前比它小的数字的和. 这下看懂样例了,可咋做啊? 如果你仔细思考一下,你会发现有个特殊的存在\(1\),它无论...

nature 线段树 CodeForces

2019-09-02

0 289

TLS 9.2 A & B

TLS 9.2A 这其实是[HNOI2006]鬼谷子的钱袋对叭... 然后你就考虑二进制是咋做到完美表示任意一个十进制数字的. 你看看它二进制下有多少位就行了. TLS 9.2B 由于\(T1\)太水了,所以我决定把它和\(T2\)放一起. 这题水的不行...我们当场想出了一堆做...

二进制 nature 差分线段树并查集

2019-09-02

0 478

ZROI#987

ZROI#987 差分+简单数学即可. 首先有个性质: 两条链相交等价于其中一条链的\(LCA\)在另一条链上. 于是我们就对每一条链的\(LCA\)都加\(1\). 最后查询每一条链的区间和即可.树剖实现. 但这样我们会算重复,就是说\((a,b)\)两条链相交我们会算\((a,b)\)一次,\...

nature 差分树链剖分线段树容斥原理

2019-09-15

0 495

ZROI#962

ZROI#962 看起来很数据结构的一道题,其实就是很数据结构... \(\Theta(nmq)\)的暴力很无脑,是个人应该都会. \(Code:\) #include <algorithm> #include <iostream> #include <cstdli...

线段树 nature 分类讨论 brute

2019-09-17

0 455