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

小码匠

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

7200

代码可运行

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

运行总次数：0

代码可运行

大家好！我是老码农。昨天是端午第一天，干了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;
}