[問題案] Rectangle Add Rectangle Sum

[maspypy]

問題概要

次を $N$ 回行う。

• $a, b, c, d, v$：$a\leq x < c$ かつ $b\leq y < d$ となる格子点 $(x,y)$ に $v$ を加算。

次に $Q$ 回答えよ。

• $a\leq x < c$ かつ $b\leq y < d$ となる格子点に加算された値の総和を求める

制約

https://judge.yosupo.jp/problem/rectangle_sum に準ずる。 ただし、重みは mod 998244353。

想定解法

長方形加算は、$[a,\infty) \times [b,\infty)$ などの $4$ 枚に分ける。 長方形取得も、$[0,a) \times [0,b)$ などの $4$ 枚に分ける。

長方形加算をすると、$[a,\infty) \times [b,\infty)$ 内の $(x,y)$ に対して $(x-a)(y-b) = xy - ay - bx + ab$ が加算される。 したがって、xy, x, y, 1 の 4 つに分けることで、4 種の長方形加算・点取得に帰着できる。

---

他所の問題も含めて手ごろな問題例が分からなかったので立てます。

[yosupo06]

良さそうです

[maspypy]

問題名が検討事項という気がしてきた。 現在 xxx Add ～～ は、add しながら求値するタイプのものしかない。

Rectangle Sum Point Add Rectangle Sum

のうち、近いのは Rectangle Sum の方か？（だとすると名前を真似しにくい。）

[maspypy]

・Rectangle Add Rectangle Sum でよいことにする ・Static Rectangle Add Rectangle Sum ・add しながら求値する問題にしてしまう（分割統治すれば、static の verify を兼ねられる）

ei1333 さんのやっているように、Static ～ が普通かな。

[SSRS-cp]

Rectangle Add Rectangle Sum にしてしまうと後で加算と求値が混じるクエリの問題を入れたくなったときに困るので、Static Rectangle Add Rectangle Sum がよさそうだと感じました。

[adamant-pwn]

Any plans for dynamic (offline) version? One can do double coordinate compression on dynamic Fenwick tree solution to pass this version https://judge.yosupo.jp/submission/96892. It's very close to TL, so perhaps you may add some anti-Fenwick tests to break it?

[MatsuTaku]

Problem StatementのQ queriseの変数表記にミスがあります． l d r u wと5つ書かれていますが，正しくは l d r uです．