145 条题解
-
-2
很简单,线段树模板题。
#include <bits/stdc++.h> #define int long long using namespace std; int x, y, a[100005]; struct node { int l, r, w, tag; } tr[400005]; inline bool inrange(int l1, int r1, int l2, int r2) { return (l1 >= l2) && (r1 <= r2); } inline bool outofrange(int l1, int r1, int l2, int r2) { return (l1 > r2) || (l2 > r1); } inline void pushup(int u) { tr[u].w = tr[u * 2].w + tr[u * 2 + 1].w; } inline void build(int u, int l, int r) { if (l == r) { tr[u].w = a[l]; return; } int mid = l + r >> 1; build(u * 2, l, mid); build(u * 2 + 1, mid + 1, r); pushup(u); } inline int query1(int u, int l, int r, int p) { if (l == r) { return tr[u].w; } else { int mid = l + r >> 1; if (p <= mid) return query1(u * 2, l, mid, p); else return query1(u * 2 + 1, mid + 1, r, p); } } inline void update1(int u, int l, int r, int p, int x) { if (l == r) { tr[u].w += x; } else { int mid = l + r >> 1; if (mid >= p) update1(u * 2, l, mid, p, x); else update1(u * 2 + 1, mid + 1, r, p, x); } } inline void maketag(int u, int len, int x) { tr[u].tag += x; tr[u].w += len * x; } inline void pushdown(int u, int l, int r) { int mid = l + r >> 1; maketag(u * 2, mid - l + 1, tr[u].tag); maketag(u * 2 + 1, r - mid, tr[u].tag); tr[u].tag = 0; } inline int query(int u, int l1, int r1, int l2, int r2) { if (inrange(l1, r1, l2, r2)) { return tr[u].w; } else if (!outofrange(l1, r1, l2, r2)) { int mid = l1 + r1 >> 1; pushdown(u, l1, r1); return query(u * 2, l1, mid, l2, r2) + query(u * 2 + 1, mid + 1, r1, l2, r2); } } inline void update(int u, int l1, int r1, int l2, int r2, int x) { if (inrange(l1, r1, l2, r2)) { maketag(u, r1 - l1 + 1, x); } else if (!outofrange(l1, r1, l2, r2)) { int mid = l1 + r1 >> 1; pushdown(u, l1, r1); update(u * 2, l1, mid, l2, r2, x); update(u * 2 + 1, mid + 1, r1, l2, r2, x); pushup(u); } } signed main() { cin >> x >> y; build(1, 1, 1); update1(1, 1, 1, 1, x); update1(1, 1, 1, 1, y); cout << query1(1, 1, 1, 1); return 0; }
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 1
- 标签
- 递交数
- 9043
- 已通过
- 4027
- 上传者