算法 0

直接二维平面暴力模拟即可，期望得分 41。

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>
const int N = 2010;
inline int rd()
{
    int k = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') k = k * 10 + (c ^ '0'), c = getchar();
    return k;
}
inline void wr(int x)
{
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
int n, m, c, T;
int a[N][N];
int x, y, z, u, v;
inline void clr() { n = m = c = T = x = y = z = u = v = 0, memset(a, 0, sizeof(a)); }
inline int up(int x, int y)
{
    for (int i = x - 1; i >= 1; --i) if (a[i][y]) return i;
    return 0;
}
inline int down(int x, int y)
{
    for (int i = x + 1; i <= n; ++i) if (a[i][y]) return i;
    return 0;
}
inline int left(int x, int y)
{
    for (int i = y - 1; i >= 1; --i) if (a[x][i]) return i;
    return 0;
}
inline int right(int x, int y)
{
    for (int i = y + 1; i <= m; ++i) if (a[x][i]) return i;
    return 0;
}
inline void solve(int x, int y)
{
    if (a[x][y] < 4) return (void)(++a[x][y]);
    a[x][y] = 0, --c;
    int p = 0;
    if (p = up(x, y)) solve(p, y);
    if (p = left(x, y)) solve(x, p);
    if (p = down(x, y)) solve(p, y);
    if (p = right(x, y)) solve(x, p);
}
int main()
{
    n = rd(), m = rd(), c = rd(), T = rd();

    for (int i = 1; i <= c; ++i)
        x = rd(), y = rd(), z = rd(), a[x][y] = z;
    
    while (T--)
    {
        int pre_c = c;
        u = rd(), v = rd();
        assert(a[u][v]);
        solve(u, v), wr(pre_c - c), putchar('\n');
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j]) wr(i), putchar(' '), wr(j), putchar(' '), wr(a[i][j]), putchar('\n');
}

算法 1

由于二维平面范围太大，无法用二维数组支撑，因此可以使用 set 套 pair<int, int> 数组记录同行与同列的水滴情况，四个方向上的临近水滴则可以用 lower_bound 找前驱和后继，按照题目规则进行递归即可。

算法 1 的实现比较卡常数，尤其是在子任务 2 当中棋盘 $2000\times 2000$，水滴方格规模 $7\times 10^5$ 的稠密情况，当连锁反应可以将所有水滴消掉的情况下即可达到上界。

一些解决方法包括但不限于：

• 使用更加快速的输入输出方式
• 在递归模拟的过程中尽可能修改全局数组和全局变量，递归函数返回类型设为 void，减少堆栈消耗空间
• 对数据范围分治，子任务 1 和 2 当中直接使用常数小的二维数组即可

期望得分 41 到 100（子任务 2 到 4 都有可能被卡掉）。

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
typedef long long i64;
inline int rd()
{
    int k = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') k = k * 10 + (c ^ '0'), c = getchar();
    return k;
}
inline void wr(int x)
{
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}

const int N = 360010, C = 750010, mask = (1 << 20) - 1;

int n, m, c, rem, T;

namespace mp
{
    int n, m; // x : [1, n] y : [1, m] 

    // row : same y col : same x
    // first : x/y second.first : y/x second.second : count
    std::set<std::pair<int, int>> row[N], col[N];

    inline void init(int _n, int _m) { n = _n, m = _m; }

    inline void insert(int x, int y, int c)
    {
        if (!c) return;
        row[y].insert(std::make_pair(x, c));
        col[x].insert(std::make_pair(y, c));
    }
    // return 0 : not exist
    inline int get_cnt(int x, int y)
    {
        std::set<std::pair<int, int>>::iterator it = col[x].lower_bound(std::make_pair(y, 0));
        if ((it == col[x].end()) || (it->first != y)) return 0;
        return it->second;
    }
    // assume exist
    inline void remove(int x, int y)
    {
        row[y].erase(row[y].lower_bound(std::make_pair(x, 0)));
        col[x].erase(col[x].lower_bound(std::make_pair(y, 0)));
    }
    inline std::pair<int, int> find_neighbor(int x, int y, int dir)
    {
        std::set<std::pair<int, int>>::iterator it;
        std::pair<int, int> ret = std::make_pair(0, 0);
        switch (dir)
        {
        case 0: // U
            it = row[y].lower_bound(std::make_pair(x, 0));
            ret = (it == row[y].begin()) ? std::make_pair(0, 0) : (--it, std::make_pair(it->first, y));
            break;
        case 1: // L
            it = col[x].lower_bound(std::make_pair(y, 0));
            ret = (it == col[x].begin()) ? std::make_pair(0, 0) : (--it, std::make_pair(x, it->first));
            break;
        case 2: // D
            it = row[y].lower_bound(std::make_pair(x + 1, 0));
            ret = (it == row[y].end()) ? std::make_pair(0, 0) : std::make_pair(it->first, y);
            break;
        case 3: // R
            it = col[x].lower_bound(std::make_pair(y + 1, 0));
            ret = (it == col[x].end()) ? std::make_pair(0, 0) : std::make_pair(x, it->first);
            break;
        default:
            break;
        }
        return ret;
    }
    inline void print_all()
    {
        for (int i = 1; i <= n; ++i)
            for (auto& v : col[i])
                wr(i), putchar(' '), wr(v.first), putchar(' '), wr(v.second), putchar('\n');
    }
}

inline void solve(int x, int y)
{
    int v = mp::get_cnt(x, y); 
    assert(1 <= v && v <= 4);
    if (v < 4) return mp::remove(x, y), mp::insert(x, y, v + 1);
    mp::remove(x, y), --rem;
    for (int dir = 0; dir < 4; ++dir)
    {
        std::pair<int, int> nxt = mp::find_neighbor(x, y, dir);
        if (nxt.first) solve(nxt.first, nxt.second);
    }
}

int main()
{
    n = rd(), m = rd(), c = rem = rd(), T = rd();
    mp::init(n, m);
    for (int i = 1; i <= c; ++i)
    {
        int x = rd(), y = rd(), a = rd();
        assert(1 <= x && x <= n), assert(1 <= y && y <= m), assert(1 <= a && a <= 4);
        mp::insert(x, y, a);
    }
    while (T--)
    {
        int pre_c = rem;
        int u = rd(), v = rd();
        solve(u, v), wr(pre_c - rem), putchar('\n');
    }
    mp::print_all();
}

算法 2

由于水滴在初始情况下是给定的，后续模拟不会出现新的水滴，因此可以基于十字链表进行预处理然后模拟，但是需要保证复杂度的正确性。直接暴力模拟的算法复杂度是平方的（同算法 0），我们可以类似并查集的路径压缩，对于仍然存在的水滴去寻找其对应方向上的实际后继，此时也需要维护已经删除水滴的后继。但是注意到算法 1 当中，递归完成某一个方向的处理之后，当前水滴其他方向的后继也会变化，因此除了删除水滴时维护后继节点的反方向后继之外，还需要在每个方向进行递归时，都重新找一次当前水滴该方向的后继。

时间复杂度瓶颈主要是对水滴的排序以及离散化的 $O(C\log C)$，其余操作均为线性的，期望得分 100。因此在 2s 的时限内其实过的比较轻松。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <array>
#include <algorithm>
typedef long long i64;
inline int rd()
{
    int k = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') k = (k << 1) + (k << 3) + (c ^ '0'), c = getchar();
    return k;
}
inline void wr(int x)
{
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 360010, C = 750010, mask = (1 << 20) - 1;
const int U = 0, L = 1, D = 2, R = 3;

int n, m, c, rem, T;

inline i64 hc(int x, int y) { return ((i64)x << 20) | y; }
struct drop
{
    int x, y, c;
    i64 hashcode;
    bool operator<(const drop &o) const { return hashcode < o.hashcode; }
} drops[C];
i64 hc_only[C];
inline int find(int x, int y) { return std::lower_bound(hc_only + 1, hc_only + c + 1, hc(x, y)) - hc_only; }

std::vector<int> X[N], Y[N];

struct node
{
    bool is_del;
    int nxt[4];
} a[C];
inline void link_LR(int l, int r) { a[l].nxt[R] = r, a[r].nxt[L] = l; }
inline void link_UD(int u, int d) { a[u].nxt[D] = d, a[d].nxt[U] = u; }

int find_nxt(int x, int dir)
{
    if (a[a[x].nxt[dir]].is_del) a[x].nxt[dir] = find_nxt(a[x].nxt[dir], dir);
    return a[x].nxt[dir];
}

inline void del_pt(int x)
{
    a[x].is_del = 1, drops[x].c = 0, --rem;
    std::array<int, 4> succ;
    for (int i = 0; i <= 3; ++i) succ[i] = find_nxt(x, i);

    if (succ[U]) a[succ[U]].nxt[D] = succ[D];
    if (succ[D]) a[succ[D]].nxt[U] = succ[U];
    if (succ[L]) a[succ[L]].nxt[R] = succ[R];
    if (succ[R]) a[succ[R]].nxt[L] = succ[L];
}

inline void solve(int x)
{
    if (!x) return;
    if (drops[x].c < 4) return (void)(++drops[x].c);
    del_pt(x);
    for (int i = 0; i <= 3; ++i) solve(find_nxt(x, i));
}

int main()
{
    n = rd(), m = rd(), c = rem = rd(), T = rd();
    for (int i = 1; i <= c; ++i)
    {
        drops[i].x = rd(), drops[i].y = rd();
        drops[i].c = rd(), drops[i].hashcode = hc(drops[i].x, drops[i].y);
        X[drops[i].x].push_back(drops[i].y), Y[drops[i].y].push_back(drops[i].x);
    }
    std::sort(drops + 1, drops + c + 1);
    for (int i = 1; i <= c; ++i) hc_only[i] = drops[i].hashcode;
    for (int i = 1; i <= n; ++i) std::sort(X[i].begin(), X[i].end());
    for (int i = 1; i <= m; ++i) std::sort(Y[i].begin(), Y[i].end());

    for (int i = 1; i <= n; ++i)
        for (size_t j = 1; j < X[i].size(); ++j)
            link_LR(find(i, X[i][j - 1]), find(i, X[i][j]));

    for (int i = 1; i <= m; ++i)
        for (size_t j = 1; j < Y[i].size(); ++j)
            link_UD(find(Y[i][j - 1], i), find(Y[i][j], i));

    while (T--)
    {
        int pre_c = rem, u = rd(), v = rd();
        solve(find(u, v)), wr(pre_c - rem), putchar('\n');
    }
    for (int i = 1; i <= c; ++i)
        if (!a[i].is_del) wr(drops[i].x), putchar(' '), wr(drops[i].y), putchar(' '), wr(drops[i].c), putchar('\n');
}