CSA Round #68 D Triangular Updates

問題ページ
CS Academy

考えたこと

• 問題文の不等式を満たす範囲が何なのか
• (R,C)を左上で幅がLの下三角行列みたいな範囲になる
• クエリ先読みすると意味のあるクエリが少ないみたいなO(Q)の方をどうにかする改善ができるようには見えない
• 範囲加算の処理をO(L^2)かけてたら当然不可能
• 範囲加算といえばimosを思い出す
• imosができればO(Q+N^2)でいけそう
• L点に+S,-Sを書く方法しか思いつかない
• https://imoz.jp/algorithms/imos_method.html を見ると差分を取る手法のところによくある形以外にも対応する方法が書いてある
• ようするにimosで累積和を取るのを逆算していけばいい
• 各クエリで6箇所に書き込めばいいので問題ない範囲
• インデックスに気をつけつつ書くと通った

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[6100][6100];
signed main(void)
{
  int n, q;
  cin >> n >> q;
  REP(i, q) {
    int y, x, l, s;
    cin >> y >> x >> l >> s;
    // if(x+l)
    dp[y][x] += s;
    dp[y][x+1] -= s;
    dp[y+l][x] -= s;
    dp[y+l+1][x+1] += s;
    dp[y+l][x+l+1] += s;
    dp[y+l+1][x+l+1] -= s;
  }

  REP(i, n+5) {
    FOR(j, 1, n+5) dp[i][j] += dp[i][j-1];
  }

  REP(i, n+5) {
    FOR(j, 1, n+5) dp[j][i] += dp[j-1][i];
  }

  // (0, i)
  REP(i, n+5) {
    FOR(j, 1, n+5) {
      dp[j][i+j] += dp[j-1][i+j-1];
    }
  }

  // (i, 0)
  FOR(i, 1, n+5) {
    FOR(j, 1, n+5) {
      dp[i+j][j] += dp[i+j-1][j-1];
    }
  }

  FOR(i, 1, n+1) {
    FOR(j, 1, n+1) {
      cout << dp[i][j];
      if(j != n) cout << " ";
    }
    cout << endl;
  }

  return 0;
}