-
线段树题目
题单
线段树1
区间相加，区间求和
#includeusing namespace std; const int N = 100010; typedef long long LL; int n, m; int w[N]; struct Node { int l, r; LL sum, add; }tr[N << 2]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { auto& root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add; right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add; root.add = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[l], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); // 注意这里 pushup(u); } } void modify(int u, int l, int r, int d) { if (l <= tr[u].l && r >= tr[u].r) { // [l, r]完全包含u对应的区间 // 处理sum和懒标记 tr[u].sum += (LL)d * (tr[u].r - tr[u].l + 1); tr[u].add += d; } else { // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, d); if (r > mid) modify(u << 1 | 1, l, r, d); // 注意这里 pushup(u); } } LL query(int u, int l, int r) { if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid) sum += query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", w + i); build(1, 1, n); int op, l, r, d; while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d%d%d", &l, &r, &d); modify(1, l, r, d); } else { scanf("%d%d", &l, &r); printf("%lld\n", query(1, l, r)); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
TJOI2009开关
一排灯初始是关闭的，每次可翻转一个区间的等的状态，每次询问一个区间内亮的等的个数。相当于是区间改状态，区间求和。
sum表示当前节点的开着的灯的个数，tag表示操作了多少次.#includeusing namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 100010; typedef long long LL; int n, m; int w[N]; struct Node { int l, r; // sum当前区间开着的灯的个数 tag标记:初始为0，操作一次变为1 int sum, tag; }tr[N << 2]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { auto& root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.tag) { left.tag ^=1, left.sum = (left.r - left.l + 1)- left.sum; right.tag ^= 1, right.sum = (right.r - right.l + 1) - right.sum; root.tag = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, 0, 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); // 注意这里 pushup(u); } } void modify(int u, int l, int r) { if (l <= tr[u].l && r >= tr[u].r) { // [l, r]完全包含u对应的区间 // 处理sum和懒标记 tr[u].sum = (tr[u].r - tr[u].l + 1) - tr[u].sum; tr[u].tag ^= 1; } else { // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r); if (r > mid) modify(u << 1 | 1, l, r); // 注意这里 pushup(u); } } LL query(int u, int l, int r) { if (l <= tr[u].l && r >= tr[u].r) { // debug(tr[u].l, tr[u].r, tr[u].sum); return tr[u].sum; } // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid) sum += query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } int main() { scanf("%d%d", &n, &m); build(1, 1, n); int op, l, r, d; while (m--) { scanf("%d", &op); if (op == 0) { scanf("%d%d", &l, &r); modify(1, l, r); } else { scanf("%d%d", &l, &r); printf("%lld\n", query(1, l, r)); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
逆序对
忠诚
区间求最小值.
#includeusing namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif typedef long long LL; const int N = 200010; struct Node { int l, r; int v; // 区间[l, r]中的最小值 }tr[N * 4]; int w[N]; void pushup(int u) // 由子节点的信息，来计算父节点的信息 { tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v); } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[l]}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点，已经被完全包含在[l, r]中了 int mid = tr[u].l + tr[u].r >> 1; int v = INT_MAX; if (l <= mid) v = query(u << 1, l, r); if (r > mid) v = min(v, query(u << 1 | 1, l, r)); return v; } // 本题不需要这个函数，这个函数是单点修改 void modify(int u, int x, int v) { if (tr[u].l == x && tr[u].r == x) tr[u].v = v; else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } int main() { int m, n; scanf("%d%d", &m, &n); for (int i = 1; i <= m; i++) scanf("%d", w + i); build(1, 1, m); int x, y; while (n--) { scanf("%d%d", &x, &y); printf("%d ", query(1, x, y)); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
无聊的数列
区间加等差数列。
转化为维护原序列的差分数列，那么区间 [ l , r ] [l,r] [l,r]加等差数列等价于在差分数列的[l]加首项, [ l + 1 , r ] [l+1, r] [l+1,r]加公差， [ r ] [r] [r]处减去末项. 转化为区间修改，区间求和的问题。#includeusing namespace std; const int N = 100010; typedef long long LL; int n, m; int w[N]; struct Node { int l, r; LL sum, add; }tr[N << 2]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { auto& root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add; right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add; root.add = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[l], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); // 注意这里 pushup(u); } } void modify(int u, int l, int r, int d) { if (l <= tr[u].l && r >= tr[u].r) { // [l, r]完全包含u对应的区间 // 处理sum和懒标记 tr[u].sum += (LL)d * (tr[u].r - tr[u].l + 1); tr[u].add += d; } else { // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, d); if (r > mid) modify(u << 1 | 1, l, r, d); // 注意这里 pushup(u); } } LL query(int u, int l, int r) { if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; // 注意这里 pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid) sum += query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } int main() { scanf("%d%d", &n, &m); //原数组 for (int i = 1; i <= n; i++) scanf("%d", w + i); // 差分数组 for (int i = n; i > 1; i--) w[i] = w[i] - w[i - 1]; build(1, 1, n); int op, l, r, k, d; while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d%d%d%d", &l, &r, &k, &d); // 差分数组 w[l] += k modify(1, l, l, k); // 差分数组 [l+1, r] += d if (l + 1 <= r) modify(1, l + 1, r, d); // 差分数组 w[r+1]-=末项 也就是 k+d*(r-l) if (r < n) modify(1, r + 1, r + 1, -(k + 1LL * d * (r - l))); } else { scanf("%d", &r); printf("%lld\n", query(1, 1, r)); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
扶苏的问题
支持区间加，区间修改，询问区间最大值
做法：打两个标记线段树2
支持区间加，区间乘，求区间和
做法：打两个标记[COCI2010-2011#6]STEP
01序列，支持单点修改一个点，询问区间内的最长无相相邻数字连续串的长度
三元上升子序列
询问 i < j < k 且 a [ i ] < a [ j ] < a [ k ] i
色板游戏
支持区间修改，询问区间内不同颜色个数。颜色个数 <= 30
小白逛公园
支持单点修改，询问区间内最长连续区间最大和
方差
支持区间加，询问区间平均数，询问区间方差
[yLOI2019]棠梨煎雪
m个01传，可能有?字符。支持单点修改，区间查询
上帝造题的七分钟2/花神游历各国
支持区间开平方，询问区间和
[SCOI2010]序列操作
给一个01序列，支持区间修改为0或1，区间取反，询问区间1的个数，询问区间最多连续1的个数
Points
二维坐标系，支持添加点，删除点，询问一个点最左边的点的坐标
-
相关阅读:
常用的css命名规则
讲述为什么要学习Adobe XD以及 Adobe XD下载安装
黑产反诈有方法，异常识别我在行—欺诈反洗钱等领域用得最多的经典算法
什么是TCP粘包？如何避免TCP粘包？
蚂蚁金服开源的这份SpringBoot笔记，两周时间在GitHub星标43.5k
当客户说价格高时我会这样做
PBR学习笔记
[英雄星球六月集训LeetCode解题日报] 第26日 并查集
Web Api的参数传递建议
java Maven入门笔记
- 原文地址：https://blog.csdn.net/dezhonger/article/details/134538131
