换新马蜂了,望周知
2025-12-17 22:14:36
发布于:广东
#include <bits/stdc++.h>
namespace cjdst{
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
template <typename T>
class Sparse_Table{
std::vector <std::vector <T>> st;
int n;
public:
Sparse_Table(int n, std::vector <T> a){
this -> n = n;
st.resize(a.size() + 5, std::vector <T>(std::__lg(n) + 5));
for(int i = 1; i <= n; i++){
st[i][0] = a[i];
}
for(int i = 1; i <= std::__lg(n); i++){
for(int j = 1; j <= n; j++){
if(j + (1 << i) - 1 > n) break;
st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
}
T query(int l, int r){
int idx = std::__lg(r - l + 1);
return std::max(st[l][idx], st[r - (1 << idx) + 1][idx]);
}
};
template <typename T>
class Fenwick_Tree{
std::vector <T> tr;
int n;
public:
Fenwick_Tree(){}
Fenwick_Tree(int n, std::vector <T> a){
tr.resize(n + 5, 0);
this -> n = n;
for(int i = 1; i <= n; i++){
tr[i] += a[i];
if(i + (i & (-i)) <= n){
tr[i + (i & (-i))] += tr[i];
}
}
}
void modify(int idx, T val){
for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
}
T query(int idx){
T ans = 0;
for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
return ans;
}
};
template <typename T>
class Segtree{
std::vector <T> tr;
std::vector <int> left, right;
std::vector <T> lazytag;
void push_up(int u){
tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
void push_down(int u){
tr[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
tr[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
lazytag[u << 1] += lazytag[u];
lazytag[u << 1 | 1] += lazytag[u];
lazytag[u] = 0;
}
void build(int u, int l, int r, std::vector <T> &a){
left[u] = l, right[u] = r;
if(l == r){
tr[u] = a[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid, a);
build(u << 1 | 1, mid + 1, r, a);
push_up(u);
}
void _modify(int u, int l, int r, T val){
if(left[u] >= l && right[u] <= r){
tr[u] += (right[u] - left[u] + 1) * val;
lazytag[u] += val;
return;
}
push_down(u);
if(right[u << 1] >= l) _modify(u << 1, l, r, val);
if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
push_up(u);
}
T _query(int u, int l, int r){
if(left[u] >= l && right[u] <= r){
return tr[u];
}
push_down(u);
T ans = 0;
if(right[u << 1] >= l) ans += _query(u << 1, l, r);
if(left[u << 1 | 1] <= r) ans += _query(u << 1 | 1, l, r);
return ans;
}
public:
Segtree(){}
Segtree(int n, std::vector <T> a){
tr.resize(n * 4 + 5);
left.resize(n * 4 + 5);
right.resize(n * 4 + 5);
lazytag.resize(n * 4 + 5);
build(1, 1, n, a);
}
void modify(int l, int r, T val){
_modify(1, l, r, val);
}
T query(int l, int r){
return _query(1, l, r);
}
};
template <typename T>
class Dynamic_Segtree{
class node{
public:
T val;
T lazytag;
T left, right;
node *lson, *rson;
node(){
val = lazytag = left = right = 0;
lson = rson = 0;
}
node(T l, T r){
val = (r + l) * (r - l + 1) / 2;
lazytag = 0;
lson = rson = 0;
left = l, right = r;
}
}*root;
void push_up(node *cur){
cur -> val = cur -> lson -> val + cur -> rson -> val;
}
void build_son(node *cur){
if(cur -> lson) return;
T l = cur -> left, r = cur -> right;
T mid = (l + r) >> 1;
cur -> lson = new node(l, mid);
cur -> rson = new node(mid + 1, r);
}
void push_down(node *cur){
T lazy = cur -> lazytag;
node *ls = cur -> lson, *rs = cur -> rson;
ls -> lazytag += lazy;
rs -> lazytag += lazy;
ls -> val += lazy * (ls -> right - ls -> left + 1);
rs -> val += lazy * (rs -> right - rs -> left + 1);
cur -> lazytag = 0;
}
void _modify(node *u, T l, T r, T val){
if(u -> left >= l && u -> right <= r){
u -> val += (u -> right - u -> left + 1) * val;
u -> lazytag += val;
return;
}
build_son(u);
push_down(u);
if(u -> lson -> right >= l) _modify(u -> lson, l, r, val);
if(u -> rson -> left <= r) _modify(u -> rson, l, r, val);
push_up(u);
}
T _query(node *u, T l, T r){
if(u -> left >= l && u -> right <= r){
return u -> val;
}
build_son(u);
push_down(u);
T ans = 0;
if(u -> lson -> right >= l) ans += _query(u -> lson, l, r);
if(u -> rson -> left <= r) ans += _query(u -> rson, l, r);
return ans;
}
public:
Dynamic_Segtree(){}
Dynamic_Segtree(T l, T r){
root = new node(l, r);
}
void modify(T l, T r, T val){
_modify(root, l, r, val);
}
T query(T l, T r){
return _query(root, l, r);
}
};
template <typename T>
class Mergable_Map{
class node{
public:
T val;
T left, right;
node *lson, *rson;
node(){
val = left = right = 0;
lson = rson = 0;
}
node(T l, T r){
val = 0;
lson = rson = 0;
left = l, right = r;
}
}*root;
void push_up(node *cur){
cur -> val = cur -> lson -> val + cur -> rson -> val;
}
void build_son(node *cur){
if(cur -> lson) return;
T l = cur -> left, r = cur -> right;
T mid = (l + r) >> 1;
cur -> lson = new node(l, mid);
cur -> rson = new node(mid + 1, r);
}
void _modify(node *u, T idx, T val){
if(u -> left == u -> right){
u -> val += val;
return;
}
build_son(u);
if(u -> lson -> right >= idx) _modify(u -> lson, idx, val);
else _modify(u -> rson, idx, val);
push_up(u);
}
node *_merge(node *u, node *&v){
if(!u) return v;
if(!v) return u;
if(u -> left == u -> right){
u -> val += v -> val;
return u;
}
u -> lson = _merge(u -> lson, v -> lson);
u -> rson = _merge(u -> rson, v -> rson);
if(u -> lson) push_up(u);
return u;
}
T _get_val(node *u, int idx){
if(!u) return 0;
if(u -> left == u -> right) return u -> val;
build_son(u);
if(u -> lson -> right >= idx) return _get_val(u -> lson, idx);
return _get_val(u -> rson, idx);
}
T _nth_element(node *u, int k){
if(!u || u -> val < k) return 0;
if(u -> left == u -> right) return u -> left;
build_son(u);
if(u -> lson -> val >= k) return _nth_element(u -> lson, k);
return _nth_element(u -> rson, k - u -> lson -> val);
}
T _get_rank(node *u, int idx){
if(!u) return 0;
if(u -> left == u -> right) return u -> val;
build_son(u);
if(u -> lson -> right >= idx) return _get_rank(u -> lson, idx);
return _get_rank(u -> rson, idx) + u -> lson -> val;
}
T _get_pre(node *u, int idx){
if(!u || !u -> val) return 0;
if(u -> left >= idx) return 0;
if(u -> left == u -> right) return u -> left;
build_son(u);
int ans = _get_pre(u -> rson, idx);
if(ans) return ans;
return _get_pre(u -> lson, idx);
}
T _get_next(node *u, int idx){
if(!u || !u -> val) return 0;
if(u -> right <= idx) return 0;
if(u -> left == u -> right) return u -> left;
build_son(u);
int ans = _get_next(u -> lson, idx);
if(ans) return ans;
return _get_next(u -> rson, idx);
}
public:
Mergable_Map(){}
Mergable_Map(T l, T r){
root = new node(l, r);
}
void modify(T idx, T val){
_modify(root, idx, val);
}
T query(){
return _query(root);
}
void merge(Mergable_Map &v){
_merge(root, v.root);
v = Mergable_Map(root -> left, root -> right);
}
T get_val(int idx){
return _get_val(root, idx);
}
T nth_element(int k){
return _nth_element(root, k);
}
T get_rank(int idx){
return _get_rank(root, idx - 1) + 1;
}
T get_pre(int idx){
return _get_pre(root, idx);
}
T get_next(int idx){
return _get_next(root, idx);
}
};
template <typename T>
class HJT_Segtree{
class node{
public:
T val;
int left, right;
node *lson, *rson;
node(){
val = left = right = 0;
lson = rson = 0;
}
};
std::vector <node*> roots;
int len;
void push_up(node *cur){
cur -> val = cur -> lson -> val + cur -> rson -> val;
}
void build(node *cur, int l, int r, std::vector <T> &a){
cur -> left = l;
cur -> right = r;
if(l == r){
cur -> val = a[l];
return;
}
int mid = (l + r) >> 1;
node *ls = new node, *rs = new node;
cur -> lson = ls;
cur -> rson = rs;
build(ls, l, mid, a);
build(rs, mid + 1, r, a);
push_up(cur);
}
void _build_new(node *cur, node *pre, int idx, T val){
int l = pre -> left;
int r = pre -> right;
cur -> left = l;
cur -> right = r;
if(l == r){
cur -> val = val;
return;
}
int mid = (l + r) >> 1;
node *ls, *rs;
if(idx <= mid){
ls = new node, rs = pre -> rson;
cur -> lson = ls, cur -> rson = rs;
_build_new(ls, pre -> lson, idx, val);
}else{
ls = pre -> lson, rs = new node;
cur -> lson = ls, cur -> rson = rs;
_build_new(rs, pre -> rson, idx, val);
}
push_up(cur);
}
T _query(node *cur, int l, int r){
if(cur -> left >= l && cur -> right <= r){
return cur -> val;
}
T ans = 0;
if(cur -> lson -> right >= l) ans += _query(cur -> lson, l, r);
if(cur -> rson -> left <= r) ans += _query(cur -> rson, l, r);
return ans;
}
public:
HJT_Segtree(){len = 0;}
HJT_Segtree(int n, std::vector <T> a){
node *root = new node;
build(root, 1, n, a);
roots.push_back(root);
}
void build_new(int pre, int idx, T val){
node *cur = new node;
_build_new(cur, roots[pre], idx, val);
roots.push_back(cur);
}
T query(int pre, int l, int r){
roots.push_back(roots[pre]);
return _query(roots[pre], l, r);
}
};
template <typename T>
class Block{
std::vector <T> a;
std::vector <T> b;
std::vector <T> lazytag;
std::vector <int> belong, left, right;
int n, len;
void push_down(int idx){
for(int i = left[idx]; i <= right[idx]; i++){
a[i] += lazytag[idx];
}
lazytag[idx] = 0;
}
void push_up(int idx){
for(int i = left[idx]; i <= right[idx]; i++){
b[i] = a[i];
}
std::sort(b.begin() + left[idx], b.begin() + right[idx] + 1);
}
public:
Block(){}
Block(int n, std::vector <T> a){
this -> n = n;
len = sqrtl(n) + 1;
this -> a.resize(n + 5);
b.resize(n + 5);
lazytag.resize(n / len + 5);
belong.resize(n + 5);
left.resize(n / len + 5);
right.resize(n / len + 5);
for(int i = 1; i <= n; i++){
this -> a[i] = a[i];
b[i] = a[i];
belong[i] = (i - 1) / len + 1;
right[belong[i]] = i;
if(!left[belong[i]]) left[belong[i]] = i;
}
for(int i = 1; left[i]; i++){
std::sort(b.begin() + left[i], b.begin() + right[i] + 1);
}
}
void modify(int l, int r, T val){
if(belong[l] == belong[r]){
push_down(belong[l]);
for(int i = l; i <= r; i++){
a[i] += val;
}
push_up(belong[l]);
return;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
for(int i = l; i <= right[curl]; i++){
a[i] += val;
}
for(int i = curl + 1; i < curr; i++){
lazytag[i] += val;
}
for(int i = left[curr]; i <= r; i++){
a[i] += val;
}
push_up(curl), push_up(curr);
}
T query(int l, int r, T val){
T ans = 0;
if(belong[l] == belong[r]){
push_down(belong[l]);
push_up(belong[l]);
for(int i = l; i <= r; i++){
if(a[i] < val) ans = std::max(ans, a[i]);
}
return ans;
}
int curl = belong[l], curr = belong[r];
push_down(curl), push_down(curr);
push_up(curl), push_up(curr);
for(int i = l; i <= right[curl]; i++){
if(a[i] < val) ans = std::max(ans, a[i]);
}
for(int i = curl + 1; i < curr; i++){
int idx = lower_bound(b.begin() + left[i], b.begin() + right[i] + 1, val - lazytag[i]) - b.begin() - 1;
if(idx >= left[i]) ans = std::max(ans, b[idx] + lazytag[i]);
}
for(int i = left[curr]; i <= r; i++){
if(a[i] < val) ans = std::max(ans, a[i]);
}
return ans;
}
};
template <typename T>
class Tree_Spliter{
std::vector <std::vector <int>> edges;
std::vector <int> dfn, dep, father, head, rank, son, siz;
Segtree <T> tr;
int n;
void dfs(int cur, int fa){
father[cur] = fa;
siz[cur] = 1;
dep[cur] = dep[fa] + 1;
for(int i:edges[cur]){
if(i == fa) continue;
dfs(i, cur);
siz[cur] += siz[i];
if(siz[son[cur]] < siz[i]) son[cur] = i;
}
}
void dfs2(int cur, int top, int &curdfn){
head[cur] = top;
curdfn++;
dfn[cur] = curdfn;
rank[curdfn] = cur;
if(!son[cur]) return;
dfs2(son[cur], top, curdfn);
for(int i:edges[cur]){
if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
}
}
public:
Tree_Spliter(){}
Tree_Spliter(int n, int root, std::vector <T> a, std::vector <std::vector <int>> v){
this -> n = n;
edges = v;
dfn.resize(n + 5);
father.resize(n + 5);
son.resize(n + 5);
siz.resize(n + 5);
head.resize(n + 5);
rank.resize(n + 5);
dep.resize(n + 5);
dfs(root, 0);
int curdfn = 0;
dfs2(root, root, curdfn);
std::vector <T> b(n + 5);
for(int i = 1; i <= n; i++){
b[i] = a[rank[i]];
}
tr = Segtree <T>(n, b);
}
int lca(int x, int y){
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]) y = father[head[y]];
else x = father[head[x]];
}
return (dep[x] < dep[y] ? x : y);
}
void modify_path(int x, int y, T val){
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]){
tr.modify(dfn[head[y]], dfn[y], val);
y = father[head[y]];
}
else{
tr.modify(dfn[head[x]], dfn[x], val);
x = father[head[x]];
}
}
if(dfn[x] > dfn[y]) std::swap(x, y);
tr.modify(dfn[x], dfn[y], val);
}
T query_path(int x, int y){
T ans = 0;
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]){
ans += tr.query(dfn[head[y]], dfn[y]);
y = father[head[y]];
}
else{
ans += tr.query(dfn[head[x]], dfn[x]);
x = father[head[x]];
}
}
if(dfn[x] > dfn[y]) std::swap(x, y);
ans += tr.query(dfn[x], dfn[y]);
return ans;
}
void modify_son(int idx, T val){
tr.modify(dfn[idx], dfn[idx] + siz[idx] - 1, val);
}
T query_son(int idx){
return tr.query(dfn[idx], dfn[idx] + siz[idx] - 1);
}
};
class dsu{
std::vector <int> father, siz;
public:
int n, unions;
dsu(){
n = 0;
}
dsu(int n){
this -> n = n;
unions = n;
father.resize(n + 5, 0);
siz.resize(n + 5, 1);
for(int i = 1; i <= n; i++){
father[i] = i;
}
}
int find(int n){
return (father[n] == n ? n : father[n] = find(father[n]));
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] < siz[y]) std::swap(x, y);
siz[x] += siz[y];
father[y] = x;
unions--;
}
};
template <typename T, int siz>
class matrix{
public:
std::vector <std::vector <T>> a;
T mod;
matrix(T m){
a.resize(siz, std::vector <T>(siz, 0));
mod = m;
}
matrix(std::vector <std::vector <T>> v, T m){
a = v;
mod = m;
}
matrix operator * (matrix <T, siz> b){
matrix <T, siz> ans(mod);
for(int i = 0; i < siz; i++){
for(int k = 0; k < siz; k++){
for(int j = 0; j < siz; j++){
ans.a[i][j] += a[i][k] * b.a[k][j] % mod;
ans.a[i][j] %= mod;
}
}
}
return ans;
}
};
namespace SCC_solver{
std::vector <int> dfn, low, scc;
std::vector <int> stack;
int curdfn, curscc;
void dfs(int cur, std::vector <std::vector <int>> &edge){
curdfn++;
dfn[cur] = curdfn;
low[cur] = curdfn;
stack.push_back(cur);
for(int i:edge[cur]){
if(scc[i] != -1) continue;
if(dfn[i] == -1){
dfs(i, edge);
low[cur] = std::min(low[cur], low[i]);
}else low[cur] = std::min(low[cur], dfn[i]);
}
if(low[cur] == dfn[cur]){
curscc++;
int tmp = stack.back();
do{
tmp = stack.back();
scc[tmp] = curscc;
stack.pop_back();
}while(tmp != cur);
}
}
std::vector <int> get_SCC(int n, std::vector <std::vector <int>> edge){
dfn.resize(n + 5, -1);
low.resize(n + 5, -1);
scc.resize(n + 5, -1);
for(int i = 1; i <= n; i++){
if(scc[i] == -1) dfs(i, edge);
}
low.clear();
dfn.clear();
stack.clear();
std::vector <int> ans;
ans.swap(scc);
curdfn = curscc = 0;
return ans;
}
};
void init(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
}
void solve(){
}
}
int main(){
cjdst::init();
int T = 1;
// std::cin >> T;
for(int _ = 1; _ <= T; _++){
cjdst::solve();
}
std::cout.flush();
return 0;
}
主打一个自定义(((
目前包含的内容:
Sparse_Table
数据结构:ST 表。
- 预处理:。
query:查询 ,,常数较小。
可以替换成区间 等。
Fenwick_Tree
数据结构:树状数组。
- 预处理:。
modify:将 增加 ,,常数极小。query:查询 ,,常数极小。
可以替换成前缀异或、前缀最值等。
Segtree
数据结构:线段树。
- 预处理:。
modify:将 的值增加 ,,常数较大。query:查询 ,,常数较大。
可以替换成区间最值,区间 次方和等。
Dynamic_Segtree
数据结构:线段树(动态开点)。
- 预处理:。
modify:将 的值增加 ,时空复杂度 ,常数极大。query:查询 ,时空复杂度 ,常数极大。
Mergable_Map
数据结构:线段树(动态开点)。
- 预处理:。
modify:将集合增加 个 ,时空复杂度 ,常数较大。- 一堆 query:时空复杂度反正都是 ,常数较大。
merge:将另一个集合合并至该集合,时空复杂度均摊 ,常数较大。
HJT_Segtree
数据结构:可持久化线段树/主席树。
- 预处理:。
build_new:新建一个数组 ,使 ,并修改 ,,常数较大。query:查询 ,,常数中等。
Block
数据结构:分块。
- 预处理:。
modify:将 的值增加 ,。query:查询 ,。
这个可以改的就很多了,几乎可以说是万能数据结构。
Tree_Spliter
数据结构:树链剖分。
- 预处理:。
modify_path:将 简单路径的所有权值增加 ,,常数极小。query_path:查询 简单路径的所有权值和,,常数较小。modify_son:将 子树的所有权值增加 ,,常数较小。query_son:查询 子树的所有权值和,,常数较小。
dsu
数据结构:并查集。
- 预处理:。
find:查询一个点所在集合的代表,。merge合并两个集合,。
可以删除路径压缩优化,用作可撤销并查集,此时查询、合并时间复杂度均为 。
matrix
数据结构:矩阵。
- 预处理:。
- 乘法:。
SCC_solver
算法:Tarjan 求 SCC。
get_SCC:对一个大小为 ,有 条边的图,求它的所有 SCC(强联通分量),。
全部评论 17
阅(((
2025-12-06 来自 上海
2经过AI判定,代码AI相似度高达80%(
1周前 来自 浙江
1这是你自己写的吗?
2025-12-14 来自 上海
0建议加一个快速傅里叶变换(((
2025-12-10 来自 上海
0buhui
2025-12-10 来自 广东
0
前摇过长(
2025-12-06 来自 云南
0?
2025-12-06 来自 广东
0
越来越逆天了,你加点数据结构也还说得过去,这他妈SCC是几个意思?(话说可以把珂朵莉树,Splay也加进去
2025-12-06 来自 浙江
0
2025-12-06 来自 浙江
0美学
2025-12-06 来自 广东
1你这名字何意味
2025-12-06 来自 广东
0
在这里的分块没调块长
2025-11-22 来自 广东
0d
2025-11-16 来自 广东
0被调成啥了这大模型
2025-11-14 来自 广东
0问号
2025-11-14 来自 广东
0
0
2025-11-14 来自 湖南
0d
2025-11-14 来自 广东
0大家好啊,我是最新款童瑞琪大模型
2025-11-09 来自 浙江
0骸刑,没我IA
2025-11-09 来自 上海
0有点但不多,说是
2025-11-08 来自 江西
0IA马蜂?
2025-11-08 来自 江西
0伪装成ai的人类
2025-11-08 来自 上海
0对。
2025-11-08 来自 广东
0
d
2025-11-08 来自 广东
0










































有帮助,赞一个