线段树

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; #define lson l, m, rt<<1 #define rson m+1, r, rt<...

题目链接：点我~~ 题意：给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足u是v的祖先, 且au*av≤k. 思路：从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节...

题目链接：点我~~ 先dfs求出欧拉序列，就是dfs遍历的顺序，然后更新是更新区间加一个数，查询是查询区间的最大值，即l[x]到r[x]间的最大值，l[x]表示第一次遍历到x点,r[x]表示遍历完有关x节点时的值，区间内就表示有关x的所有值~ #pragma comment(linker,"/STACK:1024000000,1024000000") #i...

题意:1 a:询问是不是有连续长度为 a 的空房间,有的话住进最左边 2 a b:将[a,a+b-1]的房间清空 思路:记录区间中最长的空房间 线段树操作:update:区间替换 query:询问满足条件的最左断点 //#include<bits/stdc++.h> #include<iostream> #include<c...

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报 线段树功能:update:成段替换 query:简单 hash 思路:这题数据范围很大,直接搞超时+超内存,需要离散化: 离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][20...

题目链接:点我～～ 线段树功能:update:成段增减 query:区间求和 不再是替换，而是增减，修改对应标记的增减～ //#include <bits/stdc++.h> #include<cstdio> #include<iostream> using namespace std; #define lso...

题目传送门：点我～～ 成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新 or 询问到的时候. #include <bits/stdc++.h> using namespace std; #define lson l,m,rt<&l...

poj2828 Buy Tickets 逆序维护区间和 import java.util.*; import java.math.*; public class Main { static int MAXN = 220010; static int[] sum = new int[MAXN << 2]; static in...

单点更新:最最基础的线段树,只更新叶子节点,然后把信息用 PushUP(int r)这个函数更新上来。 hdu1166 敌兵布阵 线段树功能:update:单点增减 query:区间求和 #include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 ...