信息学做题日记：鸟枪换炮，加持2个硬货，外加一道半成品的树状数组

小码匠

发布于 2024-06-11 17:58:01

480

发布于 2024-06-11 17:58:01

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是老码农。昨天是端午第一天，干了3件很重要的事。

鸟枪换炮

换了什么呢，就是下图的这个家伙，换了一台显示器。

外出集训用笔记本，在家里还是台式机爽。

最近小码匠老揉眼睛，应该是眼睛不舒服，看在眼里，决定还是跟孩子换台显示器。

现在内卷过度的结果，孩子们都是用眼过度，点灯熬油的，想把眼睛保护好太难了。

咱们学信息学的家长也要注意观察孩子，一旦发现孩子眼睛不舒服，要适当降低强度，

孩子的健康才是最重要的，如果家里用的老实显示器，也可以考虑给孩子换台显示器，

现在显示器几百块就能买一台不错。

机械键盘

第2件：换了一个机械键盘，噼里啪啦的机械键盘打起代码来，就一个字：爽。

这款小键盘正在搞活动，粉色和白色价格还是比较便宜。

原来想买个颜色艳的，直接被小码匠和匠她娘一口否决了。

就买了下面这款。

半成品的树状数组

晚上回来后，写了会作业，我看又坐在电脑前，问她是不是想再刷道题。

刷就刷吧，自己找了道题，就开干起来。

我瞄了一眼这道题，是二维线段树，二维线段树小码匠没学过。

她自己思索了一会，决定打个2维树状数组。

我提醒了她一下，我看题解区可都是二维树状数组。

你打爆了，题解区可没有能参考的东西，全都只能靠你了。

她闷声没说啥，我先试试呗。

快到9点50，她提交了一版，36分，就是下面这版代码。

毕竟是放假，需要给孩子留点放松空间。就

让小码匠去看她的湖南卫视了。

P3437 POI2006 TET-Tetris 3D

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int d, s;

struct FenwickTree {
    vector<vector<LL>> c;
    int n, m;

    FenwickTree(int n, int m) :
            n(n + 1), c(n + 2, vector<LL>(m + 2)), m(m + 1) {}

    int lowbit(int a) {
        return (-a) & a;
    }

    LL cnt(int x, int y) {
        LL ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                ans += c[i][j];
            }
        }
        return ans;
    }

    void add(int x, int y, LL w) {
        for (int i = x; i <= n; i += lowbit(i)) {
            for (int j = y; j <= m; j += lowbit(j)) {
                c[i][j] += w;
            }
        }
    }

};

void best_coder() {
    int n;
    cin >> d >> s >> n;
    FenwickTree ft(d, s);
    for (int i = 0; i < n; ++i) {
        int a, b, x, y;
        long long c;
        cin >> a >> b >> c >> x >> y;
        ++x;
        ++y;
        ft.add(x, y, c);
        ft.add(x, y + b, -c);
        ft.add(x + a, y, -c);
        ft.add(x + a, y + b, c);
    }
    long long ans = 0;
    for (int i = 1; i <= d + 1; ++i) {
        for (int j = 1; j <= s + 1; ++j) {
            ans = max(ans, ft.cnt(i, j));
        }
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}