【2017ACM-ICPC广西邀请赛】Color it

【2017ACM-ICPC广西邀请赛】Color it

【动态线段树】

问题链接:https://vjudge.net/problem/HDU-6183

Solution:

核心思路:由于查询总是对(1, y1) ~ (x, y2)这个范围内进行查询,其中x的起始固定为1,也就是说,对于任意位于y1与y2之间的上色点,只要其横坐标小于x,它就在这个区间内,于是我们可以建立线段树,用y来作为区间,线段树上每个结点的值则是这个y的区间内最小的x,由于有51中颜色【0~50】,需要维护51个这样的线段树。

上边的思路是正确的,但是因为内存限制,无法开51个1e^6 * 2的线段树,因此,我们采用动态化线段树。因为在操作线段树时,我们只需要能够由父结点寻找子节点,而不局限于必须使用index >> 1和index >> 1 | 1的方式,我们可以用两个数组来存储对于任意一个结点其左、右结点在数组中的下标,这样就可以找到一棵树所有的结点,并且,也保证了没有经历过的区间是不会存储的,具体方法如下,tree就是存放数值的线段树,rootPos数组存储51种颜色的树其根节点在tree中的位置,lrt和rrt数组分别表示以其下标作为为tree中位置的结点的左右结点在tree中的位置。

C++代码:

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1e7;
const int LIM = 2e6;
bool flag;
int tree[LIM], rootPos[51], lrt[LIM], rrt[LIM], num;

inline int mini(int a, int b) {
    return a < b ? a : b;
}

inline void clear() {
    num = 0;
    for (int i = 0; i < LIM; i++) tree[i] = INF;
    memset(rootPos, 0, sizeof rootPos);
    memset(lrt, 0, sizeof lrt);
    memset(rrt, 0, sizeof rrt);
}

inline void pushup(int rt) {
    tree[rt] = mini(tree[lrt[rt]], tree[rrt[rt]]);
}

void update(int l, int r, int si, int x, int &rt) {
    if (l > si || r < si) return;
    if (!rt) rt = ++num;
    if (l == r) {
        if (tree[rt] > x) tree[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    update(l, mid, si, x, lrt[rt]);
    update(mid + 1, r, si, x, rrt[rt]);
    pushup(rt);
}

void query(int l, int r, int qs, int qe, int x, int &rt) {
    if (!rt || flag || l > qe || r < qs) return;
    if (l >= qs && r <= qe) {
        if (tree[rt] <= x) flag = true;
        return;
    }
    int mid = (l + r) >> 1;
    query(l, mid, qs, qe, x, lrt[rt]);
    query(mid + 1, r, qs, qe, x, rrt[rt]);
}

int main(void) {
    int op, x, y1, y2, c;
    while (~scanf("%d", &op) && op != 3) {
        if (op == 0) clear();
        else if (op == 1) {
            scanf("%d%d%d", &x, &y1, &c);
            update(1, LIM, y1, x, rootPos[c]);
        } else if (op == 2) {
            scanf("%d%d%d", &x, &y1, &y2);
            int ans = 0;
            for (int i = 0; i <= 50; i++) {
                flag = false;
                query(1, LIM, y1, y2, x, rootPos[i]);
                if (flag) ans++;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}