2017-11-07
【P3372】【模板】线段树 1

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义 …

阅读更多 →
代码
2016-08-25
poj2528:线段树+离散化

http://poj.org/problem?id=2528 题意: 给出几条线段,求按顺序覆盖之后能看到得线段数目。 解法: 线段树+离散化: 但是离散化有几个问题要注意: 我建的是段树,也就是: |____|____|____| 1 2 3 这样子的。 2,3,4那组数据中比较有争议的一组是: 3 5 6 4 5 6 8 如果不离散化直接算覆盖的话,是这样的:(暂且忽略前面的1-4..) ... |____|__ …

阅读更多 →
代码 学习
2016-05-07
hiho1299&hihocoder挑战赛20-t1:打折机票 - 我是思博

话说昨天我在hihocoder找数学期望练习题时,无意中发现了hihocoder有挑战赛!发现的时候,已经开赛了有十多分钟了,我匆忙地参加了比赛。 首先,我打开了第一题: #1299 : 打折机票 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包。经过了几天的夜战,岛娘终于在 …

阅读更多 →
代码 参赛 学习
2016-04-25
poj3468:线段树初学:区间更新(求和)模板题

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 88419 Accepted: 27480 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to as …

阅读更多 →
代码 学习
2016-02-03
向线段树进发——(2)

好久没更新这个系列了,今天继续补坑。 在网上找到了一个模板题——poj3468,A simple problem   A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 84618 Accepted: 26212 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operation …

阅读更多 →
学习
2016-01-08
向线段树进发——(1)

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。——百度百科 其实对于我来说,本不应该过早接触线段树这种高端的数据结构的,然而当我得知线段树其实 …

阅读更多 →
学习
没有更多文章了...