矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）

2024-09-01 04:32
文章标签 总结 面积 线段 矩形 扫描线 周长

本文主要是介绍矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自：http://blog.csdn.net/lwt36/article/details/48908031

HDU 1542 [POJ 1151] Atlantis （矩形面积并）

  • 题意:

    求N<=100个矩形的面积并

  • 分析:

    • 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化 x 坐标就可以了
    • 扫描线: 首先把矩形按 y 轴分成两条边, 上边和下边, 对 x 轴建树, 扫描线可以看成一根平行于 x 轴的直线. 
      从 y=0 开始往上扫, 下边表示要计算面积 +1 , 上边表示已经扫过了 −1 , 直到扫到最后一条平行于 x 轴的边 
      但是真正在做的时候, 不需要完全模拟这个过程, 一条一条边地插入线段树就好了
    • 线段树: 用于动态维护扫描线在往上走时,  x 轴哪些区域是有合法面积的
    • ps: 这种线段树是不用 lazy 的, 因为不用 push_down , 为啥不用 push_down , 因为没有查询操作

  • 扫描线扫描的过程（建议配合代码模拟）

    ps:无论说的再好,都不如自己在纸上模拟一遍扫描的过程,我自己学的时候模拟了很多遍  
    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点 1→3 更新为 1

这里写图片描述

扫到第二根线, 此时 S=lcnt!=0∗h两根线之间 , 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

同上, 将蓝色的面积加到答案中去

  • 代码
//
//  Created by TaoSama on 2015-07-14
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 205, INF = 0x3f3f3f3f, MOD = 1e9 + 7;int n;
struct Seg {double l, r, h; int d;Seg() {}Seg(double l, double r, double h, int d): l(l), r(r), h(h), d(d) {}bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[N];int cnt[N << 2]; //根节点维护的是[l, r+1]的区间
double sum[N << 2], all[N];#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1void push_up(int l, int r, int rt) {if(cnt[rt]) sum[rt] = all[r + 1] - all[l];else if(l == r) sum[rt] = 0; //leaves have no sonselse sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}void update(int L, int R, int v, int l, int r, int rt) {if(L <= l && r <= R) {cnt[rt] += v;push_up(l, r, rt);return;}int m = l + r >> 1;if(L <= m) update(L, R, v, lson);if(R > m) update(L, R, v, rson);push_up(l, r, rt);
}int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endifios_base::sync_with_stdio(0);int kase = 0;while(scanf("%d", &n) == 1 && n) {for(int i = 1; i <= n; ++i) {double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);a[i] = Seg(x1, x2, y1, 1);a[i + n] = Seg(x1, x2, y2, -1);all[i] = x1; all[i + n] = x2;}n <<= 1;sort(a + 1, a + 1 + n);sort(all + 1, all + 1 + n);int m = unique(all + 1, all + 1 + n) - all - 1;memset(cnt, 0, sizeof cnt);memset(sum, 0, sizeof sum);double ans = 0;for(int i = 1; i < n; ++i) {int l = lower_bound(all + 1, all + 1 + m, a[i].l) - all;int r = lower_bound(all + 1, all + 1 + m, a[i].r) - all;if(l < r) update(l, r - 1, a[i].d, 1, m, 1);ans += sum[1] * (a[i + 1].h - a[i].h);}printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kase, ans);}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
  • 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

HDU 1255 覆盖的面积 （矩形面积交）

  • 题意:

    求N<=1000个矩形覆盖至少两次区域的面积,也就是矩形面积交

  • 分析

    • 前面的与矩形面积并类似, 不同的是 push_up 的时候要考虑至少覆盖一次 one 和至少覆盖两次 two 的更新 
      尤其是当前被覆盖了一次的时候, 由于没有 push_down 操作, 父亲节点的信息是没有同步到儿子节点的, 这样的话 push_up 就要考虑了.
    • 父亲被记录覆盖了一次, 但是如果儿子被覆盖过, 这些操作都是在这个父亲这个大区间上的, 就相当于父亲区间被覆盖了至少两次, 所以 two 和 one 都要更新

  • 代码

//
//  Created by TaoSama on 2015-10-04
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;int n;
struct Seg {double l, r, h; int d;Seg() {}Seg(double l, double r, double h, double d): l(l), r(r), h(h), d(d) {}bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[N];int cnt[N << 2];
double one[N << 2], two[N << 2], all[N];#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1void push_up(int l, int r, int rt) {if(cnt[rt] >= 2) two[rt] = one[rt] = all[r + 1] - all[l];else if(cnt[rt] == 1) {one[rt] = all[r + 1] - all[l];if(l == r) two[rt] = 0;else two[rt] = one[rt << 1] + one[rt << 1 | 1];} else {if(l == r) one[rt] = two[rt] = 0;else {one[rt] = one[rt << 1] + one[rt << 1 | 1];two[rt] = two[rt << 1] + two[rt << 1 | 1];}}
}void update(int L, int R, int v, int l, int r, int rt) {if(L <= l && r <= R) {cnt[rt] += v;push_up(l, r, rt);return;}int m = l + r >> 1;if(L <= m) update(L, R, v, lson);if(R > m) update(L, R, v, rson);push_up(l, r, rt);
}int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endifios_base::sync_with_stdio(0);int t; scanf("%d", &t);while(t--) {scanf("%d", &n);for(int i = 1; i <= n; ++i) {double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);a[i] = Seg(x1, x2, y1, 1);a[i + n] = Seg(x1, x2, y2, -1);all[i] = x1; all[i + n] = x2;}n <<= 1;sort(a + 1, a + 1 + n);sort(all + 1, all + 1 + n);int m = unique(all + 1, all + 1 + n) - all - 1;memset(cnt, 0, sizeof cnt);memset(one, 0, sizeof one);memset(two, 0, sizeof two);double ans = 0;for(int i = 1; i < n; ++i) {int l = lower_bound(all + 1, all + 1 + m, a[i].l) - all;int r = lower_bound(all + 1, all + 1 + m, a[i].r) - all;if(l < r) update(l, r - 1, a[i].d, 1, m, 1);ans += two[1] * (a[i + 1].h - a[i].h);}printf("%.2f\n", ans);}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
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 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
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104

HDU 1828 [POJ 1177] Picture（矩形周长并）

  • 题意:

    求N<=5000个矩形的轮廓长度,也就是矩形周长并

  • 分析一:

    可以用类似矩形面积并的办法, 不过这次我们不乘高, 不算面积罢了. 
    需要注意的是, 由于周长的线会被重复覆盖, 我们每次需要和上一次的作差. 
    但是这样仅仅是 x 轴的, 不过我可以再 y 轴做一次加起来就可以了

  • 演示 x 轴求长度和的部分 
    这里写图片描述

  • 代码一:

//
//  Created by TaoSama on 2015-07-15
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;int n, m[2];
int sum[N << 2], cnt[N << 2], all[2][N];
struct Seg {int l, r, h, d;Seg() {}Seg(int l, int r, int h, int d): l(l), r(r), h(h), d(d) {}bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[2][N];#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1void push_up(int p, int l, int r, int rt) {if(cnt[rt]) sum[rt] = all[p][r + 1] - all[p][l];else if(l == r) sum[rt] = 0;else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}void update(int p, int L, int R, int v, int l, int r, int rt) {if(L <= l && r <= R) {cnt[rt] += v;push_up(p, l, r, rt);return;}int m = l + r >> 1;if(L <= m) update(p, L, R, v, lson);if(R > m) update(p, L, R, v, rson);push_up(p, l, r, rt);
}int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endifios_base::sync_with_stdio(0);while(scanf("%d", &n) == 1) {for(int i = 1; i <= n; ++i) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);all[0][i] = x1, all[0][i + n] = x2;all[1][i] = y1, all[1][i + n] = y2;a[0][i] = Seg(x1, x2, y1, 1);a[0][i + n] = Seg(x1, x2, y2, -1);a[1][i] = Seg(y1, y2, x1, 1);a[1][i + n] = Seg(y1, y2, x2, -1);}n <<= 1;sort(all[0] + 1, all[0] + 1 + n);m[0] = unique(all[0] + 1, all[0] + 1 + n) - all[0] - 1;sort(all[1] + 1, all[1] + 1 + n);m[1] = unique(all[1] + 1, all[1] + 1 + n) - all[1] - 1;sort(a[0] + 1, a[0] + 1 + n);sort(a[1] + 1, a[1] + 1 + n);//      for(int i = 0; i < 2; ++i){
//          for(int j = 1; j <= m[i]; ++j) cout << all[i][j] <<' '; cout << endl;
//      } cout << endl;int ans = 0;for(int i = 0; i < 2; ++i) {int t = 0, last = 0;memset(cnt, 0, sizeof cnt);memset(sum, 0, sizeof sum);for(int j = 1; j <= n; ++j) {int l = lower_bound(all[i] + 1, all[i] + 1 + m[i], a[i][j].l) - all[i];int r = lower_bound(all[i] + 1, all[i] + 1 + m[i], a[i][j].r) - all[i];if(l < r) update(i, l, r - 1, a[i][j].d, 1, m[i], 1);t += abs(sum[1] - last);last = sum[1];}ans += t;}printf("%d\n", ans);}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
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 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
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103

  • 分析二:

    当然我们也可只对 x 轴做一次扫描线, 只要同时维护 y 轴竖线(就是求矩形面积并的时候的高)的个数,  vtl 记录竖线的个数 
    需要的注意的是竖线重合的情况, 需要再开变量 lbd,rbd 来判断重合, 避免重复计算

  • 代码二:

//
//  Created by TaoSama on 2015-07-15
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;int n;
int sum[N << 2], cnt[N << 2], vtl[N << 2];
bool lbd[N << 2], rbd[N << 2];
struct Seg {int l, r, h, d;Seg() {}Seg(int l, int r, int h, int d): l(l), r(r), h(h), d(d) {}bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[N];#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1void push_up(int l, int r, int rt) {if(cnt[rt]) {lbd[rt] = rbd[rt] = true;sum[rt] = r + 1 - l;vtl[rt] = 2;}
//叶子节点的下面的节点也是0 不这样也可以(那就要数组开大 小心RE)else if(l == r) sum[rt] = vtl[rt] = lbd[rt] = rbd[rt] = 0;else {lbd[rt] = lbd[rt << 1];rbd[rt] = rbd[rt << 1 | 1];sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];vtl[rt] = vtl[rt << 1] + vtl[rt << 1 | 1];if(rbd[rt << 1] && lbd[rt << 1 | 1]) vtl[rt] -= 2; //两条线重合}
}void update(int L, int R, int v, int l, int r, int rt) {if(L <= l && r <= R) {cnt[rt] += v;push_up(l, r, rt);return;}int m = l + r >> 1;if(L <= m) update(L, R, v, lson);if(R > m) update(L, R, v, rson);push_up(l, r, rt);
}int main() {
#ifdef LOCALfreopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endifios_base::sync_with_stdio(0);while(scanf("%d", &n) == 1) {int Min = 1e4, Max = -1e4;for(int i = 1; i <= n; ++i) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);Min = min(Min, x1);Max = max(Max, x2);a[i] = Seg(x1, x2, y1, 1);a[i + n] = Seg(x1, x2, y2, -1);}n <<= 1;sort(a + 1, a + 1 + n);//      memset(sum, 0, sizeof sum); 所有覆盖最后都被清除了 不需要初始化了
//      memset(cnt, 0, sizeof cnt);
//      memset(lbd, false, sizeof lbd);
//      memset(rbd, false, sizeof rbd);int ans = 0, last = 0;for(int i = 1; i <= n; ++i) {if(a[i].l < a[i].r) update(a[i].l, a[i].r - 1, a[i].d, Min, Max - 1, 1);ans += vtl[1] * (a[i + 1].h - a[i].h);ans += abs(sum[1] - last);last = sum[1];}printf("%d\n", ans);}return 0;
}

这篇关于矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1125949。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
hdu1689(线段树成段更新)

hdu1689(线段树成段更新)

两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...
poj 1127 线段相交的判定

poj 1127 线段相交的判定

题意： 有n根木棍，每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连，当他们之间有公共点时，就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析： 线段相交的判定。 首先，模板中的线段相交是不判端点的，所以要加一个端点在直线上的判定； 然后，端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的，所以要加是否端点相等的判断。 最后
阅读更多...
二分最大匹配总结

二分最大匹配总结

HDU 2444  黑白染色 ，二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2