「省选模拟赛」小奇的糖果 - 扫描线 + 链表

有 个彩色糖果在平面上。小奇想在平面上取一条水平的线段，并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果，使得获得的糖果并不包含所有的颜色。

题解

对纵坐标离散化。

用树状数组维护「当前」横坐标在某个区间内的糖果数量。

用链表维护「当前」某个糖果左边右边与它横坐标最近的两个糖果。

扫描线从上往下扫，初始时树状数组为满，扫到某个新纵坐标把一条直线上所有糖果从树状数组中删掉。对于每个扫描到的糖果，先把它从链表中删掉，考虑这种颜色不选，统计它左边和它右边两个与它颜色相同的糖果之间的糖果数量，更新答案。

跑扫描线之前还要先算出每两个相邻的糖果之间的答案。

题目中允许取上边或下边，只需要将纵坐标取反即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <list>

const int MAXT = 3;
const int MAXN = 100000;
const int MAXK = 100000;

struct Candy {
    int xOrigin, yOrigin;
    int x, y;
    int color;
    std::list<Candy>::iterator p;
} candies[MAXN];

bool compareByY(const Candy &a, const Candy &b) {
    return a.y < b.y;
}

bool compareByX(const Candy &a, const Candy &b) {
    return a.x < b.x;
}

int n, k, xSet[MAXN], ySet[MAXN], cx, cy;
std::list<Candy> list[MAXK];

struct BinaryIndexedTree {
    int a[MAXN];

    static int lowbit(int x) {
        return x & -x;
    }

    void update(int pos, int delta) {
        for (int i = pos; i <= n; i += lowbit(i)) a[i - 1] += delta;
    }

    int sum(int pos) {
        int result = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) result += a[i - 1];
        return result;
    }

    int query(int l, int r) {
        // printf("query(%d, %d) = %d\n", l, r, sum(r) - sum(l - 1));
        return sum(r) - sum(l - 1);
    }

    void clear() {
        memset(a, 0, sizeof(a));
    }
} bit;

inline int solve() {
    bit.clear();
    for (int i = 0; i < k; i++) list[i].clear();

    std::sort(candies, candies + n, &compareByX);
    for (int i = 0; i < n; i++) {
        candies[i].p = list[candies[i].color].insert(list[candies[i].color].end(), candies[i]);
        bit.update(candies[i].x, 1);
    }

    std::sort(candies, candies + n, &compareByY);

    int ans = 0;

    for (int i = 0; i < k; i++) {
        int last = 0;
        for (std::list<Candy>::const_iterator p = list[i].begin(); p != list[i].end(); p++) {
            ans = std::max(ans, bit.query(last + 1, p->x - 1));
            last = p->x;
        }

        ans = std::max(ans, bit.query(last + 1, n));
    }

    for (int i = 0; i < n; i++) {
        if (i == 0 || candies[i].y != candies[i - 1].y) {
            for (int j = i; j < n && candies[j].y == candies[i].y; j++) {
                bit.update(candies[j].x, -1);
            }
        }

        int l, r;

        std::list<Candy>::iterator &p = candies[i].p;
        if (p != list[candies[i].color].begin()) {
            std::list<Candy>::const_iterator prev = p;
            prev--;
            l = prev->x + 1;
        } else l = 1;

        std::list<Candy>::const_iterator next = p;
        next++;

        if (next != list[candies[i].color].end()) {
            r = next->x - 1;
        } else r = n;

        ans = std::max(ans, bit.query(l, r));

        list[candies[i].color].erase(p);
    }

    return ans;
}

int main() {
    // freopen("candy.in", "r", stdin);
    // freopen("candy.out", "w", stdout);

    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);

        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &candies[i].xOrigin, &candies[i].yOrigin, &candies[i].color), candies[i].color--;
            xSet[i] = candies[i].xOrigin;
            ySet[i] = candies[i].yOrigin;
        }

        int *xEnd, *yEnd;
        std::sort(xSet, xSet + n);
        std::sort(ySet, ySet + n);
        xEnd = std::unique(xSet, xSet + n);
        yEnd = std::unique(ySet, ySet + n);

        cx = xEnd - xSet;
        cy = yEnd - ySet;

        for (int i = 0; i < n; i++) {
            candies[i].x = std::lower_bound(xSet, xEnd, candies[i].xOrigin) - xSet + 1;
            candies[i].y = std::lower_bound(ySet, yEnd, candies[i].yOrigin) - ySet + 1;
        }

        int ans = 0;

        ans = std::max(ans, solve());
        for (int i = 0; i < n; i++) candies[i].y = -candies[i].y;
        ans = std::max(ans, solve());

        printf("%d\n", ans);
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}