[ZOJ 1610] Count the Colors

[ruiming]

ZOJ1610 - Count the Colors

题目

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.Your task is counting the segments of different colors you can see at last. Input The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.All the numbers are in the range [0, 8000], and they are all integers.Input may contain several data set, process to the end of file. Output

Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.If some color can't be seen, you shouldn't print it.Print a blank line after every dataset.

Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

Sample Output
1 1
2 1
3 1

1 1

0 2
1 1

分析

此题需要明确的一点是不能使用数组来记录颜色，数组效率很低，应该使用线段树来解决这道题。

在做关于线段树的题目的时候，要注意线段树的另一种变形点线段树。不过这道题还是用线段树来解决的。

解答此题有两个步骤：

• 建立完整线段树

  我们可以给初始线段树每个节点都赋予color = -1的属性。表示这是一颗没有颜色的节点。

• 成段更新染色

  在输入各个线段的颜色后，我们要对原线段树进行更新。可以使用color = -2来表示这是一颗混了各种颜色的树，和-1以及纯颜色区分开来。同时要注意的是，在处理一个树节点，比如题目给的第一个例子，我们经过第一步操作后(0, 4)的color值为4。接着是线段(0, 3)，color为1。此时做法是把(0, 4)的color设为-2，把其孩子(0, 2)和(2, 4)的color设为其父节点(0, 4)的color即4。接着猜开始使用(0, 3)的颜色来处理(0, 2)和(2, 4)。往下处理方式相同。

之后我们前序遍历这颗树就可以了。

如果此题使用数组，很明显使用数组将非常简单，但是效率十分低，我们每次染色都需要操作一大堆数。并且最后要遍历整个数组。如果数组范围较大，比如此题是8000，此题可能无法AC。而使用线段树，我们使用了color这个标记，为-1时表示未染色，用-2表示混杂颜色，我们在前序遍历进行到一个线段时发现color不为-2时，就不需要再继续搜索下去了。

程序

// 线段树，成段更新染色
// 不使用数组，因为数组效率太低，理解线段树！

#include <iostream>
#include <string.h>
using namespace std;
#define Maxsize 8005

int col[Maxsize];
int colCount[Maxsize];

// 顺序存储结构
struct node {
    int ld, rd;
    int color;
}Tree[Maxsize*3];

// 建立空线段树
void buildtree(int i, int a, int b) {
    Tree[i].ld = a;
    Tree[i].rd = b;
    Tree[i].color = -1;
    if (b - a == 1)	return;
    buildtree(i * 2, a, (a + b) / 2);
    buildtree(i * 2 + 1, (a + b) / 2, b);
}

// 插入 1 0 4 4
void insert(int i, int a, int b, int color) {
    int mid = (Tree[i].ld + Tree[i].rd) / 2;

    if (a <= Tree[i].ld && Tree[i].rd <= b) {
        Tree[i].color = color;
        return;
    }
    
    if (Tree[i].color != -2) {		// 代表有颜色覆盖
        Tree[i * 2].color = Tree[i].color;
        Tree[i * 2 + 1].color = Tree[i].color;
    }
    Tree[i].color = -2;
    if (b <= mid) {
        insert(i * 2, a, b, color);
    }
    else if (a >= mid) {
        insert(i * 2 + 1, a, b, color);
    }
    else {
        insert(i * 2, a, mid, color);
        insert(i * 2 + 1, mid, b, color);
    }

}

void search(int i) {
    if (Tree[i].color != -2 && Tree[i].color != -1) {
        for (int j = Tree[i].ld; j < Tree[i].rd; j++) {
            col[j] = Tree[i].color;
        }
    }
    if (Tree[i].color == -2) {
        search(2 * i);
        search(2 * i + 1);
    }
}

int main() {
    int n, m, a, b, c;
    while (cin >> n) {
        memset(colCount, 0, sizeof(colCount));
        memset(col, -1, sizeof(col));
        buildtree(1, 0, 8000);
        for (int i = 0; i < n; i++) {
            cin >> a >> b >> c;
            insert(1, a, b, c);
        }
        search(1);
        int t = -1;
        for (int i = 0; i <= 8000; i++) {
            if (col[i] == t)	continue;
            t = col[i];
            if (t != -1)	colCount[t]++;
        }
        for (int i = 0; i <= 18; i++) {
            if (colCount[i]) {
                cout << i << " " << colCount[i] << endl;
            }
        }
        cout << endl;
    }
    return 0;
}