By yusijia

Updated:

Contents
  1. 1. hdu1556
  2. 2. 分析：

hdu1556

注意所有用到push_up和push_down的位置

分析：

1 简单的线段树的成段更新，我们把它看成区间的更改和区间的求和即可，那这样我们
只要建立好线段树然后每一次进行更新，最后对每一个[i , i]区间进行求和即可

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define Lson(x) (x<<1)
#define Rson(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define MAXN 100005

struct Node{
    int left;
    int right;
    int mark;//延时标记
    int sum;
}node[MAXN * 4];

void push_up(int pos)//向上更新
{
    node[pos].sum = node[Lson(pos)].sum + node[Rson(pos)].sum;
}

void push_down(int pos)//向下更新
{
    if(node[pos].mark){
        node[Lson(pos)].mark += node[pos].mark;//传递标记
        node[Rson(pos)].mark += node[pos].mark;
        node[Lson(pos)].sum += node[pos].mark * (node[Lson(pos)].right - node[Lson(pos)].left + 1);
        node[Rson(pos)].sum += node[pos].mark * (node[Rson(pos)].right - node[Rson(pos)].left + 1);
	//因为涂颜色后的涂层可以累积，所以这里是sum += ... 而不是sum =
        node[pos].mark = 0;
    }
}


void build_tree(int left, int right, int pos)
{
    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = 0;//涂层从0开始积累
    if(left == right){//处理叶子节点
        node[pos].sum = 0;
        return ;
    }
    int mid = Mid(left, right);
    build_tree(left, mid, Lson(pos));
    build_tree(mid + 1, right, Rson(pos));
    push_up(pos);
}

void update(int left, int right, int value, int pos)
{
    if(left <= node[pos].left && node[pos].right <= right){ //该区间被包含了
        node[pos].mark += value;//区间内刷一层颜色
        node[pos].sum += value * (node[pos].right - node[pos].left + 1);
        return ;
    }
    push_down(pos);
    int mid = Mid(node[pos].left, node[pos].right);
    if(right <= mid)
        update(left, right, value, Lson(pos));
    else if(left > mid)
        update(left, right, value, Rson(pos));
    else{
        update(left, mid, value, Lson(pos));
        update(mid + 1, right, value, Rson(pos));
    }
    push_up(pos);
}

int query(int left, int right, int pos)
{
    if(node[pos].left == left && node[pos].right == right)
        return node[pos].sum;
    int mid = Mid(node[pos].left, node[pos].right);
    push_down(pos);//继续向下更新，才能完全更新完毕  
    if(right <= mid)
        return query(left, right, Lson(pos));
    else if(left > mid)
        return query(left, right, Rson(pos));
    else
        return query(left, mid, Lson(pos)) + query(mid + 1, right, Rson(pos));
}

int main()
{
    int n, a, b;
    while(scanf("%d", &n) != EOF && n){
        build_tree(1, n, 1);
        for(int i = 1; i <= n; i++){
            scanf("%d%d", &a, &b);
            update(a, b, 1, 1);
        }
        for(int i = 1; i <= n; i++){
            printf("%d", query(i, i, 1));
            if(i != n)  printf(" ");
        }
        printf("\n");
    }
    return 0;
}
Contents
  1. 1. hdu1556
  2. 2. 分析：