问题描述 给 $m$ 个区间 $[l, r]$ 以及一个数 $x$，每次在区间 $[l, r]$ 上的每一个点放置一个物品 $x$，问： $[1, n]$ 中哪个点的物品种类最多？ $[1, n]$ 中每个点数量最多的物品是哪种？ ...... 解题思路： 首先利用差分，将序列操作变成区间操作：在 $l$ 上放置一个二元组标记 $<x, 1>…

斐波那契数列的区间操作 题目：华尔街的雪 题目大意： 斐波那契序列 $f_n$ 满足 $f_0=f_1=1,f_{n+2}=f_n+f_{n+1}$，$n$ 为自然数。现在有 $n$ 个可重集合排成一列，编号分别为 $1-n$，每个集合初始包含一个数 $f_1$。请支持如下四种操作： 1. 在第l~r号集合中各加入一个斐波那契数 $f_k$ 2. …

倍增 #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 50; int n, m, s; int head[N], tot; int lg[N]; // log2(i)+1 int fa[N][22], dep[N]; struct Edge { int …

点差分 例题：P3128 [USACO15DEC]Max Flow P 题目大意： 给 $k$ 条树上路径，求哪个点被经过的次数最多、被经过了多少次。 解题思路： 树上差分算法。对于每条路径 $(a,b)$，对 num[a]++，num[b]++，num[lca(a, b)]--，num[fa[lca(a, b)]]--。 这样再做一次 dfs 后…

题目：P3292 [SCOI2016]幸运数字 题目大意： 给一颗树 $(n\le 10^4)$，每个点有一个权值。有 $q$ 组询问 $(q\le 10^5)$，问两点之间树上路径点的最大异或和。 解题思路： 首先树剖，给点重新赋 $id$；用树剖算 lca 的过程中，对每条链维护一个线性基，每次将链的线性基和答案的线性基合并。由于经过了树剖重新…