线段树
// 线段树
namespace Seg_tree {
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
typedef long long ll;
const int N = 1e5 + 5;
using std::max;
using std::min;
ll val[N << 2], laz[N << 2], maxx[N << 2], minn[N << 2];
template<class T>
const T& _max(const T& a, const T& b) { // 比较函数
return a > b ? a : b;
}
template<class T>
const T& _min(const T& a, const T& b) { // 比较函数
return a > b ? b : a;
}
void pushup(int u) { // 更新信息
val[u] = val[ls] + val[rs];
maxx[u] = max(maxx[ls], maxx[rs]);
minn[u] = min(minn[ls], minn[rs]);
}
void pushdown(int u, int l, int r) { // 下传标记
if (!laz[u]) return ;
laz[ls] += laz[u];
val[ls] += laz[u] * (mid - l + 1);
maxx[ls] += laz[u] * (mid - l + 1);
minn[ls] += laz[u] * (mid - l + 1);
laz[rs] += laz[u];
val[rs] += laz[u] * (r - mid);
maxx[rs] += laz[u] * (r - mid);
minn[rs] += laz[u] * (r - mid);
laz[u] = 0;
}
void build(int u, int l, int r) { // 建树
laz[u] = 0;
if (l == r) {
scanf("%lld", &val[u]);
maxx[u] = minn[u] = val[u];
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void add(int u, int l, int r, int lr, int rr, ll c) { // 区间加减
if (lr <= l && r <= rr) {
laz[u] += c;
ll tmp = (r - l + 1) * c;
val[u] += tmp;
minn[u] += tmp;
maxx[u] += tmp;
return ;
}
pushdown(u, l, r);
if (lr <= mid) add(ls, l, mid, lr, rr, c);
if (rr > mid) add(rs, mid + 1, r, lr, rr, c);
pushup(u);
}
ll qry(int u, int l, int r, int lr, int rr, ll* g) { // 区间查询,g 为查询的数组名
if (lr <= l && r <= rr) {
return g[u];
}
pushdown(u, l, r);
ll ans = 0;
if (lr <= mid) {
ans += qry(ls, l, mid, lr, rr, g);
}
if (rr > mid) {
ans += qry(rs, mid + 1, r, lr, rr, g);
}
return ans;
}
}
ST 表
namespace ST_RMQ {
#define MAX 1
#define MIN 0
typedef long long ll;
const int N = 1e5 + 5;
using std::max;
using std::min;
int lg[N];
ll maxx[N][20], minn[N][20];
template<class T>
const T& _max(const T& a, const T& b) {
return a > b ? a : b;
}
template<class T>
const T& _min(const T& a, const T& b) {
return a > b ? b : a;
}
void pre(int n) { // 预处理 lg
for (int i = 2; i <= n; ++ i) {
lg[i] = lg[i >> 1] + 1;
}
}
void work(int n) {
for (int j = 1; j <= lg[n]; ++ j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << j - 1)][j - 1]);
minn[i][j] = min(minn[i][j - 1], minn[i + (1 << j - 1)][j - 1]);
}
}
}
ll qry(int l, int r, int fg) { // 求最值,fg 为 1 时求最大值,fg 为 2 时求最小值
int k = lg[r - l + 1];
if (fg == MAX) return max(maxx[l][k], maxx[r - (1 << k) + 1][k]);
if (fg == MIN) return min(minn[l][k], minn[r - (1 << k) + 1][k]);
return -1;
}
}
堆
// 堆
namespace Heap {
typedef long long ll;
using std::priority_queue;
using std::vector;
using std::queue;
using std::greater;
using std::swap;
const int N = 1e5 + 5;
// 对顶堆
struct top_heap {
priority_queue<ll> q1;
priority_queue<ll, vector<ll>, greater<ll> > q2;
void insert(ll x) { // 插入
if (q1.empty()) {
q1.push(x);
return ;
}
if(x > q1.top()) q2.push(x);
else q1.push(x);
}
int K_th(int k) { // 求第 K 大的值
if (q1.size() + q2.size() < k) return -1;
while (q1.size() < k) {
q1.push(q2.top());
q2.pop();
}
while (q1.size() > k) {
q2.push(q1.top());
q1.pop();
}
return q1.top();
}
int pop_K_th(int k) { // 删除第 K 大的值
if (q1.size() + q2.size() < k) return -1;
while (q1.size() < k) {
q1.push(q2.top());
q2.pop();
}
while (q1.size() > k) {
q2.push(q1.top());
q1.pop();
}
int u = q1.top();
q1.pop();
return u;
}
};
// 可删除堆
struct del_heap {
priority_queue<ll, vector<ll>, greater<ll> > q1, q2;
void insert(ll x) { // 插入
q1.push(x);
}
void del(ll x) { // 删除
q2.push(x);
}
ll top() { // 取堆顶
while(!q2.empty() && !q1.empty() && q2.top() == q1.top()) {
q1.pop(), q2.pop();
}
return q1.top();
}
};
// 左偏树（小根堆）
struct leftist_tree {
int lson[N], rson[N], fa[N], fat[N];
ll val[N], dist[N];
int merge(int x, int y) { // 合并
if (!x || !y) {
return x | y;
}
if (val[x] > val[y] || (val[x] == val[y] && x > y))
swap(x, y);
rson[x] = merge(rson[x], y);
fat[rson[x]] = fa[rson[x]] = x;
if (dist[lson[x]] < dist[rson[x]])
swap(lson[x], rson[x]);
dist[x] = dist[rson[x]] + 1;
return x;
}
int find(int u) { // 查询堆顶的元素的标号
return (fat[u] == u || fat[u] == 0) ? u : fat[u] = find(fat[u]);
}
void earse(int u) { // 删除任意一点
int tmp = merge(lson[u], rson[u]), fu = fa[u];
fat[tmp] = fa[tmp] = fu;
fat[u] = fa[u] = tmp;
lson[fu] == u ? lson[fu] = tmp : rson[fu] = tmp;
while (fu) {
if (dist[lson[fu]] < dist[rson[fu]])
swap(lson[fu], rson[fu]);
if (dist[fu] == dist[rson[fu]] + 1)
return ;
dist[fu] = dist[rson[fu]] + 1;
fu = fa[fu];
}
}
ll top(int u) { // 查询 u 点所在堆的堆顶元素
int g = find(u);
return val[g];
}
void pop(int u) { // 弹出 u 点所在对的堆顶元素
int g = find(u);
earse(g);
}
int build(int n) { // 建树
queue<int> q;
for (int i = 1; i <= n; ++ i) {
q.push(i);
}
int x, y, z;
while (q.size() > 1) {
x = q.front(), q.pop();
y = q.front(), q.pop();
z = merge(x, y), q.push(z);
}
return q.front();
}
};
}