21
2016-09
2016-09
HDU 5877 Weak Pair (线段树+离散化+DFS)
题目链接：点我~~
题意：给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足u是v的祖先, 且au*av≤k.
思路：从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节...
09月21日
2,134
21
2016-05
2016-05
HDU 5692 Snacks (欧拉序列+线段树)
题目链接：点我~~
先dfs求出欧拉序列，就是dfs遍历的顺序，然后更新是更新区间加一个数，查询是查询区间的最大值，即l[x]到r[x]间的最大值，l[x]表示第一次遍历到x点,r[x]表示遍历完有关x节点时的值，区间内就表示有关x的所有值~
#pragma comment(linker,"/STACK:1024000000,1024000000")
#i...
05月21日
2,899
17
2016-03
2016-03
Poj3468 A Simple Problem with Integers (成段更新)
题目链接:点我～～
线段树功能:update:成段增减 query:区间求和
不再是替换，而是增减，修改对应标记的增减～
//#include <bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;
#define lso...
03月17日
2,249
17
2016-03
2016-03
Hdu1698 Just a Hook (成段更新)
题目传送门：点我～～
成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新 or 询问到的时候.
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<&l...
03月17日
2,403
17
2016-03
2016-03
线段树单点更新(二)
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...
03月17日
2,167
17
2016-03
2016-03
线段树单点更新(一)
单点更新:最最基础的线段树,只更新叶子节点,然后把信息用 PushUP(int r)这个函数更新上来。
hdu1166 敌兵布阵
线段树功能:update:单点增减 query:区间求和
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
...
03月17日
2,262