线段专题
poj3468(线段树成段更新模板题)
题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍 lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
hdu1394(线段树点更新的应用)
题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
hdu1689(线段树成段更新)
两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
hdu 1754 I Hate It（线段树，单点更新，区间最值）
题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
hdu 1166 敌兵布阵（树状数组 or 线段树）
题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
poj 1127 线段相交的判定
题意： 有n根木棍，每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连，当他们之间有公共点时，就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析： 线段相交的判定。 首先，模板中的线段相交是不判端点的，所以要加一个端点在直线上的判定； 然后，端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的，所以要加是否端点相等的判断。 最后
HDU4737线段树
题目大意：给定一系列数，F(i,j)表示对从ai到aj连续求或运算，(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd
zoj 1721 判断2条线段（完全）相交
给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
Codeforces 482B 线段树
求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作 最后判断 a[l] & a[l+1] &......&a[r] 是否= val import ja
HDU4902 线段树
n个数，m个操作， 1 L R X :区间[L,R]的数同时置为X; 2 L R X :区间[L,R]大于X的数y,置为gcd(X,y) import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;imp
fzu 2277 Change 线段树
Problem 2277 Change Time Limit: 2000 mSec Memory Limit : 262144 KB Problem Description There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.
码蹄集部分题目（2024OJ赛9.4-9.8；线段树+树状数组）
1🐋🐋配对最小值（王者；树状数组） 时间限制：1秒 占用内存：64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que
Minimal coverage -uva 覆盖线段，贪心
一道经典的贪心问题，具体方法就是将（an,bn)区间，按照an从小到大的顺序进行排序，之后从0开始， 取最大的有效区间，这里用到了结构体的快排，否则可能会超时. #include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 100000 + 10#define BOTTOM -50000 - 10str
【hdu】Just a Hook（线段树区间修改）
线段树模板题，练的是懒惰标记。 懒惰标记，就是更新一段区间的时候，如果小区间被包含在了所需要更新的区间里面，那么直接对代表这个区间的数组元素赋值，之后做一个标记（表示这个区间的子区间都需要更新）但是不继续递归（这样可以节省很多的时候）。 116571152014-09-15 14:17:26Accepted1698796MS2380K1750 BG++KinderRiven #
【POJ】Buy Tickets（思路 + 线段树）
一开始没有思路，之后问了一下学长，需要逆向处理输入。 最后一个加入队列的肯定是没有冲突的，所以我们可以从最后一个开始处理，从后往前，找第 i + 1个空着的地方。 线段树的话记录 区间中 空白位置的个数。 134418332013010521002828Accepted5368K1704MSC++1690B2014-09-14 21:19:45 #include<iost
【hdu】Billboard（线段树)
线段树的区间最大值问题，边界特殊处理一下。 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queue>#include<vector>using namespace std;#define maxn 222222int tree[maxn << 2];int w,
【Hdu】Minimum Inversion Number(逆序，线段树)
利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的，求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in
【hdu】I Hate It（线段树，结点修改求区间最大值）
线段树的模板题，还是二分递归。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#incl
【hdu】敌兵布阵（线段树，更加结点，区间求和）
最近开始刷线段树，主要围绕notonlysuccess的线段树总结刷。 结点修改还是比较简单的，不需要什么懒惰标记，直接二分递归就可以了。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vecto
ZOJ 3324 Machine(线段树区间合并）
这道题网上很多代码是错误的，由于后台数据水，他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度（就是最接近初始位置的高度），和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数，min_v 记录该区间最小高度 cover
POJ 2823 Sliding Window（线段树入门）
题意: 8 31 3 -1 -3 5 3 6 7 一串数列，有一个窗口大小为3，从数列开始往后移动，输出最大和最小值。 -1 -3 -3 -3 3 33 3 5 5 6 7 窗口大小为3 思路： 维护一个线段树，代码很详细 解题心得： 因为关键值的输入量有1000000，也就是叶节点有1000000个，总节点按理说是2000000-1，但这题得开3000000才能过
线段树 001- 概述
线段树就是一个能高效维护动态区间的一个数据结构； 他能把一个区间分成多个区间，这些区间根据它们的之间的关系形成一个树形结构。 这个过程可以构建出一颗完全二叉树。 其中线段树的操作有： 1.修改 2.查询 比如我们现在要维护一个长度为n的区间的和，那么当n=10的时候，该区间所对应的树为： 可以发现每个节点代表一个区间，每个节点存的是该区间的和；
【UVALive】6709 Mosaic 二维线段树
传送门：【UVALive】6709 Mosaic 题目大意： 每次选择矩阵中的一个点，求以他为中心，边长为D（D一定是奇数）的矩阵中的最小值min和最大值max，输出ans =（min+max）/ 2（向下取整）。然后将该点的值修改为ans。 题目分析： 赤果果的二维线段树单点修改、区间查询。 又一次学习了线段树，发现原来所有的更新操作全部放在二维中即可。 很不错，一定要经常看看，温
【CodeForces】266E More Queries to Array... 线段树
E. More Queries to Array... time limit per test 5 seconds memory limit per test 256 megabytes input standard input output standard output You've got an array, consisting of n
【FZU】1921 栀子花开 线段树果题
Problem 1921 栀子花开 Accept: 216 Submit: 745 Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 这是一个栀子花开的季节，也是一个离别的季节，四年一千多个日日夜夜，那校园的角角落落，留下了我们沉思的身影；那上百次的成绩排名表，印证了我们深深浅浅不断进步的