您正在查看 "线段树" 分类下的文章 2010-09-21 14:27 题意：在空间给定n个立方体，求这n个立方体重合三次以上的体积
分析：可以按求平面上n个矩形面积重合三次以上的面积来求，比赛还剩50分钟的时候看这题，也差不多知道个大概，只是感觉在Z轴上不好处理，仓促敲了个代码（决赛肯定不敢敲），结果是显然的，后来教主过了，说是把枚举Z轴，突然之间晃然大悟，刚看题的时候我还想Z轴范围出这么小肯定原因，咋后来就给忘了这个藏匿其中的细节呢，哎，还是自身功力太浅...
|
2010-09-15 10:33 关于此题偶只有用无语来形容了，做这道题花费了很大精力，CE几次，MLE几次，WA无数次（三十次以上吧），先说说我的情况：
1.我用set存储每行的列值，在用upper_bound查询某一行中比某一个值大的第一个值时，
set<int>::iterator it=*st[ Ans_row ].upper_bound( node[i].col+1); 如果是这样的话，VS2008会报错，
后来写成这样也就是printf("%d %d\n", y[ Ans_row ], *st[ Ans_row ].upper_bound(node[i].col));
直接输出才不报错，而且经过测试发现，如果是单个set即不是set数组就 |
2010-09-02 12:49
/*PKU 1442
题意：给定n个整数和m个操作，每个操作有一个指定的时间，在第i 个操作时找出整数序列中1->第i个操作指定的位置区间中的第i小的数：
算法：离散化+线段树，也可以用堆来做，需要注意的是可能会有相同数字出现, 有空试试堆的做法*/
#include <iostream>
|
2010-08-27 21:59
线段树+DP
题意:给定n个整数的序列,求最长的一个子序列A, 满足条件|A(i)-A(i-1)|<=d,d为给定的一个正整数,注意:子序列有可能不连续
算法:对序列排序+离散化,再建立线段树,从后往前操作,假设以当前值为第一个数开始的最长的子序列, 那么则答案为在线段树中查询满足条件的最长的子序列,然后在线段树中进行更新即可.
#include |
2010-08-25 22:24 题意：给定一个区间，和n条线段，每条线段一个起始点和一个终点，并且每条线段有一个权值，求选出一些线段覆盖给定的区间，并且要求权值和最小..
算法：把线段按右边端点（左端点也行）从小到大进行排序行，建一棵线段树，每次根据当前线段从左到右进行更新操作，
ps:想好上面的思路后，总是有种感觉可能会是错的，不过还是直接敲了代码，十分钟敲完代码，过了样例提交，WA，果断肯定是算法有问题，突然想到不能覆盖的情况是输出-1,这个我没有处理，BS，改了改代码，AC..爽哉...
|
2010-08-25 21:08
线段树优化(注意:这里有一个二分方法死活不行,用另外一种二分才过了)
题意:在一条直线上给定n个火车站台,给从第一个站台到其它站台之间的距离,给出三种火车票价,和每种票价可能乘坐的距离范围,求从一个站台到另外一个站台的最小费用,有一个trick就是st可能大于ed…
#include <iostream>
#i |
2010-08-25 21:06
题意：在一个序列中（1到n共n个数）找出一个子序列，满足条件
Mary0 > Mary1 < Mary2 > Mary3 < ... 子序列不一定是连续的
算法：从后向前dp,因为n<30000所以得进行优化，我用线段树进行优化，
先建立一颗线段树，然后从后向前查找每个值在排序以后的ID,然后在线段树中查询已经更新的值中找最大值(因为是从后向前进行的 |
2010-07-26 20:25 其实此题用矩形面积并就可以解决,不过因为面积并已经做过,不想直接套模板,写了一种插入的算法,在线段树上用height大的覆盖height小的,因为昨天晚上一个小bug,而编辑器又没法调试,加上已经快脑残的情况下,只好留着今天再来做了,改了一个变量就A了,在排序那里错把n写成index去了,哦还有把线段树的空间改大了一点. 就直接贴代码了:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int size=80100;
struct Seg |
2010-07-26 0:43 这是来包头的第一天，在火车上面看了几道题，这是其中一道
大意：略
算法：线段树 具体的就不说了，直接看代码应该不难
ps：网吧的编程环境真烂啊
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=100010;
int n, q;
struct Seg_Tree
{
int l, r;
int len;
int leftlen,rightlen;
int ans;
}tree[3*max |
2010-07-20 20:38 题目大意：略
算法描述：首先在输入一个当前数的时候，用dp[i]表示以当前数为结尾的满足条件了序列的条数，那么以前前数结尾的满足条件的序列的条数必然可以从前面的查询可以达到，因为必须满足条件差值小于等于d,所以可以建一棵线段树进行查询，得先对每个坐标进行离散化建树，然后在<=d的前面进行查询，大概的算法是这样，具有的不再叙述;
|
2010-07-20 1:37 题目描述：略
算法：先把矩形的X轴坐标离散化，然后根据离散化后的X坐标建立线段树，对于当前的矩形i, dp[i]是依赖于
rect[j].y2 < rect[i].y1 && rect[j].x2 <rect[i].x1而进行更新的，那么可以在求dp[i]之前，把矩形i所有以下点的dp最优值求出来，（矩形以下是指rect[j].y2<rect[i].y1), 因为可以得出递推，必须先求最下的矩形的dp值，然后往上面递推，而dp[i]的值的更新是在相应的已经被离散化的X坐标线段树上进行更新（具体见代码）
dp[i]的查询操作，是在线段树上面rect[i].x1前面的 |
2010-07-15 23:06 题目大意：假如给定N个数，和M种从i[k]到j[k]排序方式，对按输入顺序给定的排序方式求选择最少的排序方式使得最后可以得到最大值。
算法：建立线段树，每次输入的时候在线段树中进行从左到右的的优化，
PS：速度成功进入前十 纪念一下
|
2010-07-14 22:01 求最长升序/降序子序列的长度一般用动态规划，一种时间复杂度为O(n*n),另外一种复杂度为O(n*logn)
这里我用了线段树处理的方法，复杂度为O(n*logn),
具体的算法：先把所有的数字进行一次从小到大排序，然后离散化建立线段树，最后实现线段树的查询和插入，查询线段树中比当前值大的数中标记值最大的数，这里标记值即为包含该点以前的最长上升/下降子序列的长度，具有代码如下：
PKU 1887 O(n*n) 63ms dp: O(n*logn) 0ms; 线段树: 15ms
|
2010-07-13 16:37 题目大意：给定n个矩形，求这n个矩形重合的面积的总和
算法：把上题矩形面积并的代码改一个数字就A了，不过花了2s的时间才过，优化的算法是每次把线段加入线段树以后，把该线段和前面一条线段在横坐标上的差乘以线段树中还被两条覆盖的线段长度，原理很简单，随便画一下就会明白
|
2010-07-12 21:18 对于求矩形面积并的题；我以前用的是矩形切割进行解决，知道可以用线段树来解决，但一直也没有具体实现，终于那天晚上，偶在晚上跑步闲瑕的时候想起来了线段树处理矩形面积并这个问题，没想到在跑了一圈之后就把大概的算法想好了，今天就想到把这道题做一下，
算法描述：把所有线段的纵坐标从小到大进行排序，并且存储每一条线段，标记该线段是矩形的左线段还是右线段，然后就开始建立线段树，这里与平时做线段树的时候有点不同了，这里的线段树所建立起来的区间不一定是整数，可能有小数的情况，就相当于把所有的线段分 |
| | |
