虚空と光明のディスクール(HARD MODE) - jin_matakich 強化コンテスト(extended) F

かしこいかわいいBIT．

解法

X方向の加算，Y方向の加算に分ける．
それぞれについて，左(上)との差を考えると，区間への加算，区間和を求めることができればいいと分かる．
これはBITやSegment Treeでできる．imos法+累積和でもできるらしい．

コード

ライブラリ部分は省略しています．

// Wrongri-La Shower

#include <cstdio>
#include <array>

typedef long long ll;

template <typename T, int n>
class BIT{};

template <typename T, int n>
class CuteCleverBIT{};

int W, H, N, Q;
// bits: X, bits2: Y
CuteCleverBIT<ll,3000> bits[3001], bits2[3001];
ll map[3001][3001];

int main(){
    scanf("%d %d %d %d", &W, &H, &N, &Q);

    for(int i=0;i<N;i++){
        int x, y, a;
        scanf("%d %d %d", &x, &y, &a);

        int l = std::max(x-a+1, 1), r = std::min(x+a-1, W),
            t = std::max(y-a+1, 1), b = std::min(y+a-1, H);

        bits[y].add(l, l+1, a-(x-l));
        bits[y].add(l+1, x+1, 1);
        bits[y].add(x+1, r+2, -1);

        bits2[x].add(t, t+1, a-(y-t));
        bits2[x].add(t+1, y, 1);
        bits2[x].add(y, y+1, -(a-1));
        bits2[x].add(y+1, y+2, a-1);
        bits2[x].add(y+2, b+2, -1);
    }

    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            map[i][j] = bits[i].sum(j+1);
        }
    }

    for(int i=1;i<=W;i++){
        for(int j=1;j<=H;j++){
            map[j][i] += bits2[i].sum(j+1);
        }
    }

    for(int i=0;i<Q;i++){
        int x, y;
        scanf("%d %d", &x, &y);

        printf("%lld\n", map[y][x]);
    }
}