树状数组
cpp
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n, T{});
}
void add(int i, const T &v) {
while(i<n) {
a[i]+=v;
i+=i&-i;
}
}
T get(int i) {
T ans{};
while(i>0){
ans+=a[i];
i-=i&-i;
}
return ans;
}
T range(int l, int r) {
return get(r)-get(l-1);
}
int selectKth(const T &k) {
int x = 0;
T cur{};
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && cur + a[x + i - 1] <= k) {
x += i;
cur = cur + a[x - 1];
}
}
return x;
}
};
对顶堆
这里维护第k大(维护第k小对元素取负即可)
- 建立一大一小两个堆
- 记住小维护大,大维护小
- 小根堆用于维护值前k大的元素
- 大根堆用于维护值小于k大的元素
- 维护,一个堆超大小了就取出来丢到另外一个堆即可
- 插入的话,小于小根堆堆顶的元素就丢到大根堆,否则相反,然后维护
- 记得python中大根堆都是相反数
- 记得每次插入完都要update一下,有些题目会改变k,所以就不写死了insert后调用update
反悔堆
要最小化决策数量,一种决策代价低但是效果差(1-10效果,同种之间值不定),一种决策代价高但是效果好(100-200效果),我们先贪心的选代价低的决策,然后当不行的时候反悔最小的效果的决策并改为高代价的决策
cpp
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
vector<int> end(2);
end[0]=target;
end[1]=0;
stations.push_back(end);
sort(stations.begin(),stations.end());
priority_queue<int> q;
int cnt=0;
int now=0;
for(auto s:stations){
int pos=s[0],fuel=s[1];
if(pos>target)break;
int d=pos-now;
while(!q.empty()&&startFuel<d){
startFuel+=q.top();
q.pop();
cnt++;
}
if(startFuel<d)return -1;
startFuel-=d;
now=pos;
q.push(fuel);
}
return cnt;
}
};
ST表
cpp
int A[N], f[__lg(N) + 1][N];
void init(int n) {
for (int i = 1; i <= n; ++i)
f[0][i] = A[i];
for (int i = 1; i <= __lg(n); ++i)
for (int j = 1; j + (1 << i) - 1 <= n; ++j)
f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int s = __lg(r - l + 1);
return max(f[s][l], f[s][r - (1 << s) + 1]);
}
线段树
Lazy线段树
todo
标记数组_do
用于打上标记_down
用于下传标记_up
用于维护树的信息上传
只需要修改这三个函数以及查询函数即可
一般会对有todo的区间节点依然加上todo影响的值,这样查询的时候就不用额外处理下标
对于多种lazy标记的时候,需要注意两个点:
- 规定好标记处理的先后顺序
- 尽量利用标记的相互转化,而不是直接下传
cpp
int val[N];
int node[N << 2], todo[N << 2];
void _do(int p, int size, int v)
{
node[p] += v * size;
todo[p] += v;
}
void _down(int p, int l, int r)
{
if (l >= r)
return;
int size = r - l + 1;
_do(p * 2, size - size / 2, todo[p]);
_do(p * 2 + 1, size / 2, todo[p]);
todo[p] = 0;
}
void _up(int p)
{
node[p] = node[p * 2] + node[p * 2 + 1];
}
void build(int p, int l, int r)
{
if (l == r)
{
node[p] = val[l];
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
_up(p);
}
void update(int p, int l, int r, int L, int R, int v)
{
if (L <= l and r <= R)
{
_do(p, r - l + 1, v);
return;
}
int mid = (l + r) >> 1;
_down(p, l, r);
if (mid >= L)
update(p * 2, l, mid, L, R, v);
if (mid < R)
update(p * 2 + 1, mid + 1, r, L, R, v);
_up(p);
}
i64 query(int p, int l, int r, int L, int R)
{
if (L <= l and r <= R)
{
return node[p];
}
_down(p, l, r);
i64 ans = 0;
int mid = (l + r) >> 1;
if (mid >= L)
ans += query(p * 2, l, mid, L, R);
if (mid < R)
ans += query(p * 2 + 1, mid + 1, r, L, R);
return ans;
}
单调栈
维护NGE,或者递增递减关系(比如子序列最大字典序)等
平衡树
基于pb_ds版
cpp
#ifdef USE_PD
#include <ext/pb_ds/assoc_container.hpp> //容器库
#include <ext/pb_ds/tree_policy.hpp> //各种树
#include <ext/pb_ds/hash_policy.hpp> //哈希表
using namespace __gnu_pbds;
#endif
cpp
tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> p;
// upper_bound的实际定义为寻找序列中第一个不满足比较函数的元素,lower_bound的实际定义为寻找序列中最后一个满足比较函数的元素
// 故std::less改为std::less_equal(允许元素重复)后两函数返回结果互换
// 同时find函数无法正确使用
int n = read();
for (int i = 0; i < n; i++)
{
int opt = read(), x = read();
if (opt == 1)
{
p.insert(x);
}
if (opt == 2)
{
auto ops = p.upper_bound(x);
p.erase(ops);
}
if (opt == 3)
{
print(p.order_of_key(x) + 1);
}
if (opt == 4)
{
print(*p.find_by_order(x - 1));
}
if (opt == 5)
{
auto pos = p.upper_bound(x);
print(*(--pos));
}
if (opt == 6)
{
auto pos = p.lower_bound(x);
print(*(pos));
}
}