G 九峰与蛇形填数

其他题目题解点击此处，持续更新……

思路

这个题目直接暴力就可以了，不需要用啥线段树。
每个点每次取值肯定是最后一个覆盖到它区域的值，所以直接取那个数即可。
然后还有一个细节就是剪枝，预处理区域的大小，如果这个点不在这个区域直接break。不用赋值了。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 3000 + 10, M = 2010, INF = 0x3f3f3f3f;
int n, m;
int x[N], y[N], k[N],g[M][M];

bool inside(int t, int a, int b)
{
    return a <= t && t <= b;
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin >> n >> m;
    int x1 = INF, y1 = INF, x2 = 0, y2 = 0;
    _rep(i, 1, m)
    {
        cin >> x[i] >> y[i] >> k[i];
        x1 = min(x1, x[i]);
        y1 = min(y1, y[i]);
        x2 = max(x2, x[i] + k[i] - 1);
        y2 = max(y2, y[i] + k[i] - 1);
    }

    _rep(i, 1, n) _rep(j, 1, n) For(l, m, 1)
    {
        if (!inside(i, x1, x2) || !inside(j, y1, y2)) break;
        if (inside(i, x[l], x[l] + k[l] - 1) && inside(j, y[l], y[l] + k[l] - 1))
        {
            g[i][j] = k[l] * (i - x[l]);
            if (i - x[l] & 1) g[i][j] += y[l] + k[l] - j;
            else g[i][j] += j - y[l] + 1;
            break;
        }
    }

    _rep(i, 1, n) _rep(j, 1, n) printf("%d%s", g[i][j], j == n ? "\n" : " ");

    return 0;
}