模板
2026-08-16 20:42:13
发布于：上海
98阅读
0回复
0点赞
目录[1]
持续更新中。
现在是线段树。
可以在评论区提出改进建议，比如格式之类。
图论
最短路
堆优化 dij[2]
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector <pair <int, int> > g[N];
int n, m, s;
int vis[N], dis[N];
void Dijkstra(int s) {
memset(dis, 0x3f,sizeof dis);
dis[s] = 0;
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
pq.push({0, s});
while (pq.size()) {
auto cur = pq.top();
pq.pop();
if (vis[cur.second]) continue;
vis[cur.second] = 1;
int w = cur.first, u = cur.second;
for (auto i : g[u]) {
if (dis[i.first] > w + i.second) {
dis[i.first] = w + i.second;
pq.push({dis[i.first], i.first});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
} Dijkstra(1);
}
未优化 dij[3]
#include <bits/stdc++.h>
using namespace std;
int e[1005][1005], dis[1005], vis[1005];
void Dijkstra(int n, int s) {
for (int i = 0; i <= n; i++) dis[i] = 1e9;
dis[s] = 0;
for (int i = 1; i < n; i++) {
int u = 0;
for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] < dis[u]) u = j;
vis[u] = 1;
for (int v = 1; v <= n; v++) if (e[u][v]) if (dis[v] > dis[u] + e[u][v]) dis[v] = dis[u] + e[u][v];
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
int tmp = e[u][v] ? e[u][v] : 1e9;
e[u][v] = min(tmp, w);
} Dijkstra(n, s);
return 0;
}
SPFA[4]
#include <bits/stdc++.h>
using namespace std;
int dis[500005], vis[500005];
vector <pair <int, int> > g[500005];
void SPFA(int n, int m, int s, int t) {
queue <int> q;
q.push(s);
vis[s] = 1, dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (auto [v, w] : g[u]) if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
} cout << dis[t];
}
signed main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = 1e9;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
g[x].push_back({y, z});
} SPFA(n, m, s, t);
return 0;
}
Floyd[5]
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0;
int dis[105][105], a[10005];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> dis[i][j];
for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
cout << ans;
return 0;
}
树论
树的直径[6]
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n, c, dep[N];
vector <int> g[N];
void dfs(int u, int fa) {
for (auto &v : g[u]) {
if (v == fa) continue;
dep[v] = dep[u] + 1;
if (dep[v] > dep[c]) c = v;
dfs(v, u);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
} dfs(1, 0);
dep[c] = 0; dfs(c, 0);
cout << dep[c];
return 0;
}
LCA[7]
#include <bits/stdc++.h>
using namespace std;
vector <int> g[500005];
int st[500005][25], dep[500005], n, q, s;
void init(int u, int fa) {
dep[u] = dep[fa] + 1;
st[u][0] = fa;
for (int i = 1; i <= 20; i++) st[u][i] = st[st[u][i - 1]][i - 1];
for (int v : g[u]) if (v != fa) init(v, u);
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int dis = dep[x] - dep[y];
for (int i = 0; i <= 20; i++) if ((dis >> i) & 1) x = st[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--) if (st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];
return st[x][0];
}
int main() {
cin >> n >> q >> s;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
} init(s, 0); while (q--) {
int x, y;
cin >> x >> y;
cout << LCA(x, y) << '\n';
}
return 0;
}
树上差分[8]
#include <bits/stdc++.h>
using namespace std;
int n, k, ans, st[1000005][25], dep[1000005], diff[1000005], val[1000005];
vector <int> g[1000005];
void init(int u, int fa) {
dep[u] = dep[fa] + 1;
st[u][0] = fa;
for (int i = 1; i <= 20; i++) st[u][i] = st[st[u][i - 1]][i - 1];
for(int v : g[u]) if (v != fa) init(v, u);
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int dis = dep[x] - dep[y];
for (int i = 0; i <= 20; i++) if ((dis >> i) & 1) x = st[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--) if (st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];
return st[x][0];
}
void dfs(int u, int fa) {
val[u] = diff[u];
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
val[u] += val[v];
} ans = max(ans, val[u]);
}
int main() {
cin >> n >> k;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
} init(1, 0); while (k--) {
int u, v;
cin >> u >> v;
int lca = LCA(u, v);
diff[u] += 1, diff[v] += 1, diff[lca] -= 1, diff[st[lca][0]] -= 1;
} dfs(1, 0); cout << ans;
return 0;
}
换根DP[9]
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
vector <int> g[N];
int n, sz[N], dp[N];
void init(int u, int fa, int d) {
sz[u] = 1;
dp[1] += d;
for (int v : g[u]) {
if (v == fa) continue;
init(v, u, d + 1);
sz[u] += sz[v];
}
}
void dfs(int u, int fa) {
for (int v : g[u]) {
if (v == fa) continue;
dp[v] = (dp[u] - sz[v]) + (n - sz[v]); // v子树 + 不包含v子树
dfs(v, u);
}
}
signed main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
} init(1, 0, 0), dfs(1, 0);
cout << max_element(dp + 1, dp + n + 1) - dp;
return 0;
}
生成树
最小生成树[10]
#include <bits/stdc++.h>
using namespace std;
vector <pair <int, pair <int, int> > > g;
int fa[5005];
int root(int x) {
if (fa[x] == x) return x;
return fa[x] = root(fa[x]);
}
void merge(int x, int y) {
int rx = root(x), ry = root(y);
if (rx != ry) fa[rx] = ry;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
g.push_back({z, {x, y}});
} sort(g.begin(), g.end());
int sum = 0, cnt = 0;
for (auto p : g) {
if (root(p.second.first) != root(p.second.second)) {
merge(p.second.first, p.second.second);
cnt++;
sum += p.first;
}
} cout << (cnt == n - 1 ? to_string(sum) : "orz");
return 0;
}
动态规划
背包
01背包[11]
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[30005];
int w[10005], v[10005];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[m] << endl;
return 0;
}
完全背包[12]
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int dp[10000005];
int w[10005], v[10005];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[m] << endl;
return 0;
}
多重背包[13]
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, tot;
int dp[10000005];
int w[1000005], v[1000005], c[1000005];
signed main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
int wei, val, k;
cin >> wei >> val >> k;
for (int j = 1; j <= k; j *= 2) {
w[++tot] = j * wei;
v[tot] = j * val;
k -= j;
} if (k) {
w[++tot] = k * wei;
v[tot] = k * val;
}
}
for (int i = 1; i <= tot; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[m] << endl;
return 0;
}
分组背包[14]
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <pair <int, int> > v[35];
int dp[205][205];
signed main() {
int m, n, t;
cin >> m >> n >> t;
for (int i = 1; i <= n; i++) {
int w, c, p;
cin >> w >> c >> p;
v[p].push_back({w, c});
} for (int i = 1; i <= t; i++) for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
for (auto &[w, c] : v[i])
if (j >= w) dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + c);
} cout << dp[t][m];
return 0;
}
序列DP
最长上升子序列[15]
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n, a[MAXN], dp[MAXN];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j <= i; j++) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
} cout << *max_element(dp + 1, dp + n + 1);
return 0;
}
最长公共子序列[16]
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n, dp[MAXN][MAXN], temp;
char a[MAXN], b[MAXN];
int main() {
cin >> a + 1 >> b + 1;
for (int i = 1; i <= strlen(a + 1); i++) {
for (int j = 1; j <= strlen(b + 1); j++) {
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
} cout << dp[strlen(a + 1)][strlen(b + 1)];
return 0;
}
字符串
字符串哈希[17]
// 字符串哈希 <=> 一套字符串匹配问题统称 变形应用可以解决一系列匹配问题
// 进制哈希 -> 全串匹配 n个中有多少个不同 -> 压缩成数字 -> O(n) 判等
// 看成一个P进制数字，对质数M取模
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const ull P1 = 1331;
const ull P2 = 131;
int main() {
int n;
cin >> n;
set <pair <int, int> > hash;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
ull h1 = 0, h2 = 0;
for (int j = 0; j < s.size(); j++) h1 = h1 * P1 + s[j], h2 = h2 * P2 + s[j];
hash.insert({h1, h2});
} cout << hash.size();
return 0;
}
最长回文子串[18]
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define N 5000005
const ull P = 131;
int n;
ull p[N]/* P进制幂次 */, h1[N], h2[N]/* 正反向哈希的前缀和数组 */;
char s1[N], s2[N]; // 正反字符串
ull get_hash1(int l, int r) {
return h1[r] - h1[l - 1] * p[r - l + 1];
}
ull get_hash2(int l, int r) {
return h2[r] - h2[l - 1] * p[r - l + 1];
}
int check_odd(int i) {
// 最远延伸距离
int l = 0, r = min(i - 1, n - i);
int max_R = 0; // 最大单侧回文半径
while (l <= r) {
int mid = (l + r) / 2;
// 整个子串
int L1 = i - mid;
int R1 = i + mid;
int L2 = n - R1 + 1;
int R2 = n - L1 + 1;
if (get_hash1(L1, R1) == get_hash2(L2, R2)) max_R = mid, l = mid + 1;
else r = mid - 1;
} return 2 * max_R + 1;
}
int check_even(int i) {
// 最远延伸距离
int l = 1, r = min(i, n - i);
int max_R = 0; // 最大单侧回文半径
while (l <= r) {
int mid = (l + r) / 2;
// 整个子串
int L1 = i - mid + 1;
int R1 = i + mid;
int L2 = n - R1 + 1;
int R2 = n - L1 + 1;
if (get_hash1(L1, R1) == get_hash2(L2, R2)) max_R = mid, l = mid + 1;
else r = mid - 1;
} return 2 * max_R;
}
int main() {
string s;
cin >> s;
n = s.size();
p[0] = 1;
for (int i = 1; i <= n; i++) {
s1[i] = s[i - 1];
s2[i] = s[n - i];
p[i] = p[i - 1] * P;
} for (int i = 1; i <= n; i++) {
h1[i] = h1[i - 1] * P + s1[i];
h2[i] = h2[i - 1] * P + s2[i];
} int max_len = 0; // 最长回文子串
for (int i = 1; i <= n; i++) { // 枚举对称中心
max_len = max({max_len, check_odd(i), check_even(i)}); // i 为中心 | i&i+1 为中心
} cout << max_len;
return 0;
}
PMT及其应用
最长公共前后缀[19]
#include <bits/stdc++.h>
using namespace std;
int pmt[4000005];
void get_pmt(string &p) {
int n = p.size();
for (int i = 1, j = 0; i < n; i++) {
while (j && p[i] != p[j]) j = pmt[j - 1];
if (p[i] == p[j]) j++;
pmt[i] = j;
}
}
int main() {
string s;
while (cin >> s) {
get_pmt(s);
deque <int> vec;
for (int j = s.size(); j; j = pmt[j - 1]) vec.push_front(j);
for (int i : vec) cout << i << " ";
cout << endl;
}
return 0;
}
KMP[20]
#include <bits/stdc++.h>
using namespace std;
#define MOD 10007
int pmt[1000005];
void get_pmt(string &p) {
int n = p.size();
for (int i = 1, j = 0; i < n; i++) {
while (j && p[i] != p[j]) j = pmt[j - 1];
if (p[i] == p[j]) j++;
pmt[i] = j;
}
}
int kmp(string &s, string &p) {
int ans = 0;
for (int i = 0, j = 0; i < s.size(); i++) {
while (j && s[i] != p[j]) j = pmt[j - 1];
if (s[i] == p[j]) j++;
if (j == p.size()) ans++, j = pmt[j - 1];
} return ans;
}
int main() {
int t;
cin >> t;
string s1, s2;
while (t--) {
cin >> s1 >> s2;
get_pmt(s1);
cout << kmp(s2, s1) << endl;
}
return 0;
}
数据结构
ST表[21]
#include <bits/stdc++.h>
using namespace std;
int n, m, st[100005][15];
void init() {
int k = log2(n);
for (int j = 1; j <= k; j++) for (int i = 1; i <= n - (1 << j) + 1; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> st[i][0];
init();
while (m--) {
int l, r;
cin >> l >> r;
int len = log2(r - l + 1);
cout << max(st[l][len], st[r - (1 << len) + 1][len]) << '\n';
}
return 0;
}
树状数组[22]
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t1[200005], t2[200005], n, q;
int lowbit(int x) {
return x & (-x);
}
void add1(int x, int y) {
for ( ; x <= n; x += lowbit(x)) t1[x] += y;
}
void add2(int x, int y) {
for ( ; x <= n; x += lowbit(x)) t2[x] += y;
}
int query(int x, int t[]) {
int ans = 0;
for ( ; x >= 1; x -= lowbit(x)) ans += t[x];
return ans;
}
void add(int l, int r, int k) {
add1(l, k), add1(r + 1, -k);
add2(l, l * k), add2(r + 1, -(r + 1) * k);
}
void ans(int l, int r) {
cout << (r + 1) * query(r, t1) - query(r, t2) - l * query(l, t1) + query(l, t2) << '\n';
}
signed main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
add(i, i + 1, x);
} while (q--) {
int opt;
cin >> opt;
if (opt == 1) {
int l, r, k;
cin >> l >> r >> k;
add(l, r, k);
} else {
int l, r;
cin >> l >> r;
ans(l, r);
}
}
return 0;
}
并查集[23]
#include <bits/stdc++.h>
using namespace std;
int fa[10005];
int root(int x) {
if (fa[x] == x) return x;
return fa[x] = root(fa[x]);
}
void merge(int x, int y) {
int rx = root(x), ry = root(y);
if (rx != ry) fa[rx] = ry;
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) fa[i] = i;
while (q--) {
int z, x, y;
cin >> z >> x >> y;
if (z == 1) merge(x, y);
else cout << (root(x) == root(y) ? 'Y' : 'N') << '\n';
}
return 0;
}
Trie
字典树[24]
#include <bits/stdc++.h>
using namespace std;
int tree[3000005][65], idx;
int pass[3000005];
int num(char c) {
if ('A' <= c && c <= 'Z') return c - 'A';
if ('a' <= c && c <= 'z') return c - 'a' + 26;
return c - '0' + 52;
}
void insert(string& s, int v) {
int p = 0;
for (char &c : s) {
int u = num(c);
if (!tree[p][u]) tree[p][u] = ++idx;
p = tree[p][u];
pass[p] += v;
}
}
int query(string& s) {
int p = 0;
for (char &c : s) {
int u = num(c);
if (!tree[p][u]) return 0;
p = tree[p][u];
} return pass[p];
}
void init() {
for (int i = 0; i <= idx; i++) {
pass[i] = 0;
for (int j = 0; j < 65; j++) tree[i][j] = 0;
} idx = 0;
}
int solve() {
init();
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
insert(s, 1);
} while (q--) {
string s;
cin >> s;
cout << query(s) << endl;
}
return 0;
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
最大异或值对[25]
#include <bits/stdc++.h>
using namespace std;
#define N 100000 * 31 + 5
int tree[N][2], idx;
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int u = (x >> i) & 1;
if (!tree[p][u]) tree[p][u] = ++idx;
p = tree[p][u];
}
}
int query(int x) {
int p = 0, ans = 0;
for (int i = 30; i >= 0; i--) {
int u = (x >> i) & 1;
if (tree[p][!u]) {
ans += (1 << i); p = tree[p][!u];
} else p = tree[p][u];
} return ans;
}
int main() {
int n, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
insert(x);
ans = max(ans, query(x));
} cout << ans;
return 0;
}
最长异或路径[26]
#include <bits/stdc++.h>
using namespace std;
#define N 100000 * 31 + 5
int tree[N][2], idx;
vector <pair <int, int> > g[N];
int dep[N];
void dfs(int u, int fa) {
for (auto [v, w] : g[u]) {
if (v == fa) continue;
dep[v] = dep[u] ^ w;
dfs(v, u);
}
}
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int u = (x >> i) & 1;
if (!tree[p][u]) tree[p][u] = ++idx;
p = tree[p][u];
}
}
int query(int x) {
int p = 0, ans = 0;
for (int i = 30; i >= 0; i--) {
int u = (x >> i) & 1;
if (tree[p][!u]) {
ans += (1 << i); p = tree[p][!u];
} else p = tree[p][u];
} return ans;
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int x, y, z;
cin >> x >> y >> z;
g[x].push_back({y, z});
g[y].push_back({x, z});
} dfs(1, 0); int ans = 0; for (int i = 1; i <= n; i++) {
insert(dep[i]);
ans = max(ans, query(dep[i]));
} cout << ans;
return 0;
}
线段树
单点修改区间查询最值[27]
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[200005];
int tree[800005];
void pushUp(int u) {
tree[u] = max(tree[u * 2], tree[u * 2 + 1]); // 左右子树中更大之值
}
void build(int u, int l, int r) { // 建树：节点 u 管辖区间 [l, r]，初始化每个结点的区间最大值
// 递归边界，直至区间长为 1
if (l == r) {
tree[u] = a[l];
return ;
}
// 递归建树
int mid = (l + r) / 2;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
// 从下层回溯，上传区间最值
pushUp(u);
}
// 单点修改：将位置 pos 更新为 val
void update(int u, int l, int r, int pos, int val) {
// 递归边界
if (l == r) {
tree[u] = max(tree[u], val);
return ;
}
// 分治更新
int mid = (l + r) / 2;
if (pos <= mid) update(u * 2, l, mid, pos, val);
if (pos > mid) update(u * 2 + 1, mid + 1, r, pos, val);
// 上传更新信息
pushUp(u);
}
// 区间查询 区间 [ql, qr] 中最值
// [l, r] 遍历区间 [ql, qr] 查询区间
int query(int u, int l, int r, int ql, int qr) {
// 注意到当遍历区间被查询区间包裹，其为查询区间的一部分
if (ql <= l && r <= qr) return tree[u];
// 分治查询
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid) res = max(res, query(u * 2, l, mid, ql, qr));
if (qr > mid) res = max(res, query(u * 2 + 1, mid + 1, r, ql, qr));
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (m--) {
char op;
int x, y;
cin >> op >> x >> y;
if (op == 'Q') cout << query(1, 1, n, x, y) << '\n'; // 查询区间最值
else update(1, 1, n, x, y); // 更新
}
return 0;
}
区间修改+区间查询求和 线段树[28]
#include <bits/stdc++.h>
using namespace std;
const int N = 400005;
struct node {
int l, r; // 管辖区间
long long sum; // 区间和
long long tag; // lazy 标记
} tree[4 * N];
int n, m;
long long a[N];
void pushUp(int u) {
tree[u].sum = tree[u * 2].sum + tree[u * 2 + 1].sum;
}
void applyTag(int u, long long val) {
long long len = tree[u].r - tree[u].l + 1;
tree[u].sum += (long long)len * val;
tree[u].tag += val; // 继承父亲的 lazy 标记
}
void pushDown(int u) {
if (tree[u].tag != 0) {
applyTag(u * 2, tree[u].tag);
applyTag(u * 2 + 1, tree[u].tag);
tree[u].tag = 0;
}
}
// 每个节点初始化
void build(int u, int l, int r) {
tree[u].l = l, tree[u].r = r, tree[u].tag = 0;
// 递归边界
if (l == r) {
tree[u].sum = a[l];
return ;
}
// 分支递归
int mid = (l + r) / 2;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
// 回溯合并
pushUp(u);
}
// 区间修改 [ql, qr] 每个数 +val
void update(int u, int ql, int qr, long long val) {
// 递归边界
if(ql <= tree[u].l && tree[u].r <= qr) {
applyTag(u, val);
return ;
}
// 向下分治修改
pushDown(u); // 往下查询需传递 lazy 标记
int mid = (tree[u].l + tree[u].r) / 2;
if (ql <= mid) update(u * 2, ql, qr, val);
if (qr > mid) update(u * 2 + 1, ql, qr, val);
pushUp(u); // 上传
}
long long query(int u, int ql, int qr) {
// 合并
if (ql <= tree[u].l && tree[u].r <= qr) return tree[u].sum;
// 往下递归分治
pushDown(u);
int mid = (tree[u].l + tree[u].r) / 2;
long long res = 0;
if (ql <= mid) res += query(u * 2, ql, qr);
if (qr > mid) res += query(u * 2 + 1, ql, qr);
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (m--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
int k;
cin >> k;
update(1, x, y, k);
} else cout << query(1, x, y) << '\n';
}
return 0;
}
全部评论 13
建议：
.语言为c++ .不要注释和多余空格（缩进的空格要有） .变量/函数等名字取首字母，变量名简短，不要特殊函数（不是自定义 .一定用<bits/stdc++.h> .数组大小要额外+5~500（整十整百数） .输入输出一定用cout/cin .同数据类型的变量要写在同一行，要在全局！！！ .要写using namespace std; .注意:即将写'{'时不要额外换行 .缩进为4个空格 .数组循环从1开始 .不要有多余空格，但要有四格缩进 .不用写“ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);”[如有雷同纯属巧合（还记得我今天给你发的雷霆语句吗）
2天前 来自 山西
1权值树
#include<bits/stdc++.h> using namespace std; int sum[10000005]; int a[10000005]; vector<int> v; int man(int l,int r,int x,int y,int rp){//区间求和 if(y<l||r<x)return 0; if(x<=l&&y>=r)return sum[rp]; int mid=(l+r)/2; int a=man(l,mid,x,y,rp*2); int b=man(mid+1,r,x,y,rp*2+1); return a+b; } void manba(int l,int r,int x,int y,int rp){//单点修改 if(l==x&&r==x){ sum[rp]+=y; return; } int mid=(l+r)/2; if(x<=mid) manba(l,mid,x,y,rp*2); if(x>mid) manba(mid+1,r,x,y,rp*2+1); sum[rp]=sum[rp*2]+sum[rp*2+1]; } int manbaout(int l,int r,int x,int rp){//单点查询 if(l==r)return sum[rp]; int mid=(l+r)/2; if(x<=mid) return manbaout(l,mid,x,rp*2); else return manbaout(mid+1,r,x,rp*2+1); } int wcis(int l,int r,int k,int rp){//按排名查找函数（寻找第 k 小） if(l==r)return r; int mid=(l+r)/2; if(k<=sum[rp*2]) return wcis(l,mid,k,rp*2); else return wcis(mid+1,r,k-sum[rp*2],rp*2+1); } int frv(int x,int m){//前驱查找 int k=man(1,m,1,x-1,1); if(!k) return -1; return wcis(1,m,k,1); } int bav(int x,int sum,int m){//后继查找 int k=man(1,m,1,x,1)+1; if(k>sum) return -1; return wcis(1,m,k,1); } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int m=v.size(); int sum=0; for(int i=1;i<=n;i++){ int x=a[i]; int idx=lower_bound(v.begin(),v.end(),x)-v.begin()+1; if(i==1){ cout<<x<<endl; manba(1,m,idx,1,1); sum++; continue; } if(manbaout(1,m,idx,1)>0){ cout<<0<<endl; manba(1,m,idx,1,1); sum++; continue; } int fr=frv(idx,m); int ba=bav(idx,sum,m); int ans; if(fr==-1)ans=v[ba-1]-x; else if(ba==-1)ans=x-v[fr-1]; else ans=min(x-v[fr-1], v[ba-1]-x); cout<<ans<<e4天前 来自 广东
1补
else ans=min(x-v[fr-1], v[ba-1]-x); cout<<ans<<endl; manba(1,m,idx,1,1); sum++; } return 0;4天前 来自 广东
0
线段树区修
#include<bits/stdc++.h> #define int long long using namespace std; int a[1000005],sum[4000005],b[4000005]; void man(int x){ sum[x]=sum[x*2]+sum[x*2+1]; } void manba(int x,int y,int c){ if(x==y){ sum[c]=a[x]; return; } int mid=(x+y)/2; manba(x,mid,2*c); manba(mid+1,y,2*c+1); man(c); } void wcis(int c,int l,int r){//push_bown b[c*2]+=b[c]; b[c*2+1]+=b[c]; sum[c*2]+=b[c]*l; sum[c*2+1]+=b[c]*r; b[c]=0; } void manbaout(int x,int y,int d,int l,int r,int c){//区间查询 if(x<=l&&y>=r){ sum[c]+=d*(r-l+1); b[c]+=d; return; } int mid=(l+r)/2; wcis(c,mid-l+1,r-mid); if(x<=mid){ manbaout(x,y,d,l,mid,c*2); } if(y>mid){ manbaout(x,y,d,mid+1,r,c*2+1); } man(c); } int wcismbo(int x,int y,int l,int r,int c){//区间修改 if(x<=l&&y>=r){ return sum[c]; } int mid=(l+r)/2,ans=0; wcis(c,mid-l+1,r-mid); if(x<=mid){ ans+=wcismbo(x,y,l,mid,c*2); } if(y>mid){ ans+=wcismbo(x,y,mid+1,r,c*2+1); } return ans; } signed main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; manba(1,n,1); for(int i=1;i<=m;i++){ int a,b,c,d; cin>>a; if(a==1){ cin>>b>>c>>d; manbaout(b,c,d,1,n,1); }else{ cin>>b>>c; cout<<wcismbo(b,c,1,n,1)<<endl; } } return 0; }4天前 来自 广东
1线段树单修
#include<bits/stdc++.h> using namespace std; int a[100005],sum[400005]; void man(int x){//求值 sum[x]=sum[x*2]+sum[x*2+1]; } void manba(int l,int r,int rp){//建树 if(l==r){ sum[rp]=a[l]; return ; } int mid=(l+r)/2; manba(l,mid,rp*2); manba(mid+1,r,rp*2+1); man(rp); } int manbaout(int l,int r,int x,int y,int rp){//查询 if(x<=l&&y>=r)return sum[rp]; int ans=0; int mid=(l+r)/2; if(x<=mid) ans+=manbaout(l,mid,x,y,rp*2); if(y>mid) ans+=manbaout(mid+1,r,x,y,rp*2+1); return ans; } void wcis(int l,int r,int x,int y,int rp){//更改 if(l==x&&r==x){ sum[rp]=y; return ; } int mid=(l+r)/2; if(x<=mid) wcis(l,mid,x,y,rp*2); if(x>mid) wcis(mid+1,r,x,y,rp*2+1); man(rp); } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; memset(sum,127,sizeof(sum)); manba(1,n,1); for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; if(a==1){ cout<<manbaout(1,n,b,c,1)<<endl; }else{ wcis(1,n,b,c,1); } } return 0; } //模板，适用于查询x,y区间所有权值和，改变第x个数为y4天前 来自 广东
1
有帮助，赞一个