对于每一个操作打上时间戳，对于 \(T\) 时刻的询问，即为询问路径上比 \(T-c\) 的值小的数有几个。
直接树剖上维护权值树状数组即可。
给定一棵树，\(n\) 个顶点，每个点有一个宝石，类型为 \(W_i\)，约定 \(W_i \le m\)。你有一个收集器，可以收集至多 \(c\) 个宝石，并且收集顺序必须为 \(P_1,P_2...P_c\)，其中 \(P_1\sim P_c\) 互不相同。有 \(q\) 次询问，每次询问一条有向路径 \(s_i \to t_i\)，求依次最多可以收集多少宝石。
第一步转化，将 \(P_1\sim P_c\) 对应到 \(1\sim n\) 上，并将对应的 \(W\) 修改，即使得收集顺序为 \(1\sim n\)。
对于一条 \(u\to v\) 的路径，可以拆分为 \(u\to lca\) ，\(lca\to v\) 两条链。
倍增预处理 \(f[0/1][u][i]\) 表示在 \(u\) 到根的路径上权值为 \(W_i \pm 2^i\) 的点最近在哪里。
对于上链，先找到 \(1\) 的位置，然后直接能跳就跳，跳到深度不小于 \(lca\) 的点。
对于下链，二分答案，设最大能跳到 \(mid\)。在下链上找到最近的 \(mid\)，往上能跳就跳，知道跳到深度不小于 \(lca\) 为止。再判断两个点的大小关系即可。
本题题意大概是给出一棵 \(n\) 个节点的树以及 \(m\) 条有向路径，每个点 \(i\) 都有一个权值 \(w_i\)，如果某条路径包含了 \(i\) 号节点，并且 \(i\) 号节点是该路径上的第 \(w_i\) 个节点的话就会对这第 \(w_i\) 个点产生贡献。问最后每个点的贡献和。
同样，对于一条路径 \(u\to v\) ，拆分为上链和下链，对于上链，观察点 \(i\) 能观察到的条件为 \(dep[i]-dep[u]=w[i]\)，对于下链，条件为 \(dep[u]-dep[lca]+dep[i]-dep[lca]=w[i]\)。
移项，\(dep[u] = dep[i] - w[i]\)，\(dep[u]-2\times dep[lca]=w[i]-dep[i]\)。
直接开两个桶对于每一条路径加一下即可。线段树合并，可持久化线段树应该都可以。
给定数组 \(a\)，多次询问给定 \(b,x,l,r\)，求 \(\max_{i=l}^r b \oplus (a_i+x)\)。
贪心题。
设 \(t=a_i+x\) 使得 \(t \oplus b\) 最大。将 \(b\) 二进制拆分。
从高往低位选，显然，\(t_i=b_i\oplus1\) 是最好的，但是这样会使得无法找到一个合法的 \(a_i+x\)。
令 \(sum=\sum_{j>i} t_j\times 2^j\)。
若合法，\(a_i+x\in [sum+(b_i \oplus 1)\times 2^i,sum+(b_i \oplus 1)\times 2^i+2^i-1]\)。
那么 \(a_i\) 的范围也出来了。如果在 \([l,r]\) 中找得到这样的 \(a_i\)，答案的 \(i\) 位即为 \(1\)。
手动模拟一下，每一次会确定 \(t\) 第 \(i\) 位的 \(0/1\)。然后可持久化线段树就好了。
给定 \(n\) 个任务，每个任务有开始和结束时间和优先级。问某一秒正在运行的所有任务的前 \(k\) 小优先级之和，强制在线。
把任务差分，开始时间 +1，结束时间 -1。单点查询即为查询前缀和。可以把操作离线全部执行一遍，建出每一个时刻的主席树，询问时直接查。
整体二分做的。模板题。
你需要维护 \(n\) 个可重整数集，集合的编号从 \(1\) 到 \(n\)。
这些集合初始都是空集，有 \(m\) 个操作：
1 l r c：表示将 \(c\) 加入到编号在 \([l,r]\) 内的集合中2 l r c：表示查询编号在 \([l,r]\) 内的集合的并集中，第 \(c\) 大的数是多少。
整体二分，只不过变成了区间加，区间查。很简单的一道题。注意第 \(k\) 大和第 \(k\) 小的区别，看似不大，其实要考虑清楚很多东西。
还是整体二分题。这道题说明了整体二分不止能用于查询第 \(k\) 小类的问题。
给出一个环形序列，被分为 \(m\) 段。有 \(n\) 个国家，序列的第 \(i\) 段属于国家 \(o_i\)。接下来有 \(k\) 次事件，每次给环形序列上的一个区间加上一个正整数。每个国家有一个期望 \(p_i\)，求出每个国家在序列上所有位置的值的和到达 \(p_i\) 的最早时间（或报告无法达到）。
同样，二分答案，对于二分到的 \(mid\)，将 \(mid\) 之前的操作都执行一遍。对于跨越首尾的操作仅需拆成两段即可。
给定一棵 \(n\) 个节点的树，每条边有边权，求出树上两点距离小于等于 \(k\) 的点对数量。
点分治模板，在 \(x\) 处 solve 一下，把当前统计到的答案加一下，但是会有不跨越 \(x\) 点的路径，在其每一个子树 \(v\) 中都减去即可。描述显然不清晰，看代码即可。
整体二分+二维树状数组模板。
几乎与 MET-Meteors 相同的题。
小 A 的楼房外有一大片施工工地，工地上有 \(N\) 栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小 A 在平面上 \((0,0)\) 点的位置，第 \(i\) 栋楼房可以用一条连接 \((i,0)\) 和 \((i,H_i)\) 的线段表示，其中 \(H_i\) 为第 \(i\) 栋楼房的高度。如果这栋楼房上任何一个高度大于 \(0\) 的点与 \((0,0)\) 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了 \(M\) 天。初始时，所有楼房都还没有开始建造，它们的高度均为 \(0\)。在第 \(i\) 天，建筑队将会将横坐标为 \(X_i\) 的房屋的高度变为 \(Y_i\)（高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做）。请你帮小 A 数数每天在建筑队完工之后，他能看到多少栋楼房？
很精妙的题。对于每一个点，权值位连接 \((0,0)\) 所形成的斜率记为 \(k_i\)，显然，小A 能看到的一定是确定的一段 \(a_i\) 连续递增的点。因为区间是固定的，并且发现一个区间内的答案可以通过两个子区间用某种方式进行转移。所以可以考虑到线段树做法。线段树中只需要维护两个值，一个是区间最大值，还有一个是区间序列长度。查询答案显然是第一个节点（根节点）的答案。问题在于如何修改。单说修改固然简单，问题在于修改过后的 pushup 。区间最大值显然取左右儿子的最大值，答案则需要用左儿子的答案 + 右儿子中从左儿子的最大值开始递增的答案。写一个 qry 函数，发现这个函数是单侧递归的。
const int N = 1e5 + 5;
int n, m;
double k[N];
struct SGT
{
int ans[N << 2];
double mx[N << 2];
int qry(int l, int r, double val, int id)
{
if (l == r) return val < k[l];
int mid = l + r >> 1;
if (mx[id << 1] <= val) return qry(mid + 1, r, val, id << 1 | 1);
else return qry(l, mid, val, id << 1) + ans[id] - ans[id << 1];
}
void mdf(int l, int r, int x, double k, int id)
{
if (l == r) return mx[id] = k, ans[id] = 1, void();
int mid = l + r >> 1;
if (x <= mid) mdf(l, mid, x, k, id << 1);
else mdf(mid + 1, r, x, k, id << 1 | 1);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
ans[id] = ans[id << 1] + qry(mid + 1, r, mx[id << 1], id << 1 | 1); // 左区间的不受影响，右区间可能会因为更改产生变化
}
} T;
signed main()
{
cin >> n >> m;
R(i, 1, m)
{
int x, y;
read(x, y);
k[x] = y * 1.0 / x;
T.mdf(1, n, x, k[x], 1);
printf("%d\n", T.ans[1]);
}
return 0;
}
上代码更直观。
标签：二分,专题,dep,楼房,线段,路径,lca,数据结构 From： https://www.cnblogs.com/cyyhcyyh/p/17988574