线段专题

线段树单点修改的应用

思路：对初始状态进行建树，然后这题就相当于查询第一个合法的位置，并且对其值进行修改，整个题目要求维护的是区间最大值，很显然可以使用线段树。 #include <bits/stdc++.h>using namespace std;const int N = 2e6 + 5;typedef long long ll;typedef pair<ll, ll> pll;typedef arra

[HDU 5029] Relief grain （树链剖分+线段树）

HDU - 5029 其实这道题最大的难点不是树链剖分，而是怎么维护某个点被那些颜色染过，染过多少次如果在线段树维护的话，很难做到，估计得树套树，而且空间会炸好在这题是离线的，可以使用差分的思想来维护对一段区间[l,r]染色 c，相当于在这段区间左端点 l打上 c标志，右端点 r+1打上 -c标志然后扫一遍整个区间（依照 dfs序扫一遍整棵树），期间不断维护一颗线段树线段树

HDU 4791二分+线段树

13长沙现场赛水题二分+线段树二分出页数的所在位置线段树查找后面区间最小值 #include "stdio.h"#include "string.h"#include "math.h"#include "stdlib.h"struct comp{int l,r,mid;__int64 min;} data[400100];__int64 a[100100],b[1

HDU 4578 线段树多lazy操作

2013ACM-ICPC杭州赛区全国邀请赛线段树裸题 bzoj 1798 升级版 add记录加 mul记录乘 sum[1] 记录一次方和 sum[2] 记录二次方和 sum[3] 记录三次方和公式推导出： sum[3]=(sum[3]+(sqr3(m)*len())%mod + (3*m*sum[2])%mod + (3*sqr2(m)*sum[1])%mod) %m

HDU 4553 线段树双关键字区间合并

用两个关键字记录，分别为屌丝时间和女神时间若屌丝约，更新屌丝时间若女神约，更新屌丝和女神时间学习，则两个全部清空 #include "stdio.h"#include "string.h"struct Data{int l,r,x1,x2,l1,l2,r1,r2;}data[400010];int Max(int a,int b){if (a<b) return b

HDU 3974 线段树（将树映射到区间）

第一次写将树映射到区间的线段树。。。线段树部分很简单主要是将原有的关系树根据BOSS关系从新编号以便把每个BOSS所带领的员工全部压入一个连续区间内然后记录每个BOSS的起始编号和他的最后一名的员工的编号然后用线段树成端更新，单点查找即可 #include "stdio.h"#include "string.h"struct node{int l,r,val,l

HDU 5372 线段树

给出两种操作：第i个0：在x位置插入一个长度为i的线段，并输出该线段共覆盖了多少之前加入的线段 1：删除第i次插入的线段官方题解：对于新插入的线段，查询有多少个线段左端点大于等于该线段的左端点。再查询有多少个线段的右端点大于该线段右端点，两者之差就是答案。用两个树状数组搞定。时间复杂度nlog 思路很好理解，直接用一个线段树记录区间的左端点和右端点即可 #include

【线段树】hdu 1394 Minimum Inversion Number

题意:求Inversion后的最小逆序数思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解线段树功能:update:单点增减 query:区间求和 #include<iostream>#include<algorithm>using namespace std;int sum[10001],x[5001];void pushup(int

poj2528 Mayor's posters 【线段树】

题目难度还好只要知道流程了，代码基本能写出来大致思路是：对所有区间的端点进行排序，并离散化节省空间时间然后读入每一张海报，更新所表示的区间，最后统计能看得到多少张海报比较坑的是，这题卡scanf，用c++交过的，载上一篇文章 https://www.byvoid.com/blog/fast-readfile C++中的快速读取 #include <map>#include <se

整型数组处理算法（十一）请实现一个函数：线段重叠。[风林火山]

请实现一个函数：线段重叠; 输入多个一维线段,求出这些线段相交的所有区域(也用线段表示); 一条线段用两个值表示(x0,x1), 其中x1>x0; 比如：输入线段数组[(2,4),(1.5,6),(0.5,3.5),(5,7),(7.5,9)], 输出线段数组[(1.5,4),(5,6)] 实现代码如下： float** GetSegmentOverlap(float**

HDU1823 二维线段树求最大值

Luck and Love Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5382 Accepted Submission(s): 1344 Problem Description 世界上上最远的距离不是相

TOJ 4369 ZOJ 3632 Watermelon Full of Water / 线段树优化DP

Watermelon Full of Water 时间限制(普通/Java):3000MS/9000MS 运行内存限制:65536KByte 描述 Watermelon is very popular in the hot summer. Students in ZJU-ICPC Team also love watermelon very much and they

TOJ 4399 Deal with numbers / 线段树成段更新

Deal with numbers 时间限制(普通/Java):10000MS/30000MS 运行内存限制:65536KByte 描述 There are n numbers with the corresponding NO.1-n, and the value of the i-th number is xi. Define three operations:

二维线段树模版

HDU 4819 二维线段树模版题 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int INF = 999999999;const int maxn = 810;int a[maxn][maxn];int st_min[maxn<<2][maxn<<2];

hdu4288 线段树+离线化+离散化

题目看起来很麻烦，其实不难。题意是个坑，以为输入是有序的，结果居然不是，WA了好多遍。维护五颗记录和的线段树，分别对应对5取余的值，这个题简单的地方就在于查询时每次都查整个区间，所以只需要输出根节点即可，目测如果进一步改成子区间会难很多。维护时，相当于将每个点都作为一个区间，然后两个区间合并时，左孩子的记录可直接用，右孩子的记录需要参考左区间元素个数才能判断在整个区间的位置，公式很好推

poj2886 线段树

线段树题目，思路不难，关键是F(p)，很难想清楚是神马，表示看了别人的题意解析才知道神马意思。反素数这玩意果断决定打表了，以后比赛随时带着这玩意得了。另外注意的是，反素数的因子个数不是连续变化的，有可能依次增加好几个因子，这点特别注意下。其他就是依次剔除人了，知道人物当前位置和当前人物长度可轻易推出下次出列的人物位置，依次将人物出列直到答案的值。代码： #include <iostr

spoj3267 D-query 主席树(可持久化线段树)

题目链接题意：给n个数，m次查询,求[l,r]之间不重复数的个数。思路：主席树。用一个map记录每个值在当前操作下最新的位置，从前往后插入主席树。对于查询[l,r]，窝们在root[ l ]下查询在r之前的不重复数的个数。详见代码： /*********************************************************file name: spoj3267.

AutoCAD 利用二维线段通过旋转得到三维图

步骤： 1.画轮廓线。Line直线/Circle圆/@相对坐标/Ucs确定原点 2.45°直线画法：界面左下角图标--开启极轴追踪--右键--增量角选45°。再画直线时，当直线移动到45度时会显示射线延长线，确定即可。 3.修改线段长度：length--T--输入总长度--选择对象。 4.删除部分线段：break--删除第一点与第二点之间的线段（有时可能需要构造交点实现删除）。 5.

poj 1269 Intersecting Lines（计算几何：线段相交）

给出两条线段，问对应哪三种情况：不相交，重合，相交于一点代码如下: /* ***********************************************Author :yinhuaEmail :yinwoods@163.comFile Name :poj1269.cppCreated Time :2014年12月02日星期二

hdu4288--Coder--线段树--离线处理+离散化+想法！

做过的线段树做到现在收获最大的一题～～～以后还要多做几遍～～～学会了左加右减的位移思想，学会了离线处理数据，学会了用lower_bound或者upper_bound寻找hash中某个数值所在的数组下标～～整道题的思路和注释都写在代码里了。 //HDU 4288 线段树离线+离散化#include <cstdio>#include <

hdu 1166_线段树树状数组

这题之前用线段树做过，不过这周开始树状数组的学习，就用树状数组重新写了一遍。与线段树相比，树状数组在单个点更新和区间求和方面更有优势。另外代码也很简洁。线段树AC代码： #include <cstdiO>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define ls

Codeforces 786B Legacy 最短路+线段树

不错的题目，这次不偷qsc得了，偷个别人的 https://blog.csdn.net/diogenes_/article/details/80396914 传送门题目意思很简单，就是你有三种操作： 1 u v w 从u向v连一条权值为w的有向边 2 u L R w 从u向L至R的所有结点连一条权值为w的有向边 3 u L R w 从L至R的所有结点向u连一条权值为w的有向边首

HDU--1556 -- Color the ball [树状数组] [线段树]

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5864 Accepted Submission(s): 3122 Problem Description N个气球排成一排，从

hdu 3308线段树区域合并

区域合并时需要考虑两点 1、pushup中区域合并时最左右递增长度（llen/rlen）等于整个区域长度(r - l)时需要重新计算父区域的最左右的递增长度 2、query中需要考虑区域合并接口处是否有可能产生ans值 #include<iostream>#include<stdio.h>#include<string>#include<string.h>using namesp

hdu 1166线段树

线段树的一般模板，1.结构体数组tree来存储 2.线段树的构建函数buildTree 3.改变元素值函数update 4.查询区间内总和的函数query 全部使用递归来实现 ##################################################################### #include<iostream>#include<stdi

python 判断点和线段相交

python 判断点和线段相交 import numpy as npimport cv2import numpy as npdef point_to_line_distance(points, line_segments):# line_segments = [[549, 303], [580, 303]]# points = [565, 304]x0, y0, x1, y1=lin