[問題案] Static Range Composite

[noshi91]

Problem name: Static Range Composite

Problem

長さ $N$ の列が与えられ、各要素は $a i x + b i$ 。 $\lbrack l , r \rparen$ を合成するクエリを $Q$ 回処理

Constraint

• $0 \leq N, Q \leq 5 \times 10 ^ 5$
• $0 \leq l \leq r \leq N$
• $a _ i \neq 0$

Solution / Reference

非可換な累積和 非可換な Disjoint Sparse Table

Input

$N$ $Q$ $a 0$ $b 0$ $a 1$ $b 1$ $\vdots$ $a {N - 1}$ $b {N - 1}$ $l 0$ $r 0$ $l 1$ $r 1$ $\vdots$ $l {Q - 1}$ $r {Q - 1}$

Discussion

非可換な累積和や非可換な DST を verify できる問題が無かった気がして建てましたが見落としていたら教えてください。

[maspypy]

問題はないですね。

他の問題に合わせると l r x かなと思います。あとは大丈夫だと思います。

[maspypy]

作業者募集です。

[noshi91]

作業します。 C++ (function) なんですが、引数は vector<tuple<int, int, int>> と vector 3 つならどっちが良いでしょうか？

[noshi91]

↑ これよく分からないことを言っていますね。 a, b, l, r, x をそれぞれ 1 つの配列にするか、ab の pair の配列と lrx の tuple の配列にするか、を迷っています

[maspypy]

特に積極的な理由がないならば、問題文に合わせておくとよいのではと思いました（この場合、(a,b) が N 個と (l,r,x) が Q 個）。

[SSRS-cp]

問題文に合わせるとはどういうことでしょうか (問題文には「組 (a,b) が N 個と組 (l,r,x) が Q 個与えられます。」のように書かれるわけではないため)

他の問題にもかなり影響しそうなので丁寧に議論したほうがいいと思っています

[noshi91]

問題文というか入力形式に最も沿っているとは思います。 他の問題に関係するので色々意見聞きたいのは賛成です。

[maspypy]

「入力をどちらで与える方がいいか？ $a0 \ldots a{N-1}$ $b0 \ldots b{N-1}$ vs $a_0$ $b0$ $\vdots$ $a{N-1}$ $b_{N-1}$」 と 「solve 関数に何を与えるのがいいか？」 で判断を変える理由が特にないと思っています。

（入力の与え方については、既出の類題に準ずる（判断が難しい場合は作業者判断でよい）くらいで認識しています。）

[noshi91]

std::pair はともかくとして std::tuple がややパソコン要素がある (std::get<1>(v) とか) ので、そこが迷いどころです。 struct qeury_type { int l, r, x; }; を定義して std::vector を与えるという手もある。

[maspypy]

Function 形式は topcoder 文化から来ているらしいので、そこで十分一般的なフォーマットならばいいだろうと判断するのもありだと思います、が、私は topcoder 文化を知らないです。

solve(vector<tuple<int,int,int>>){} と書かれて、検索や AC 提出例などを見てもその入力形式を扱えない人は、 C++(Function) 機能を諦めていただくでもよい気がしますが。

[hos-lyric]

(tuple が好きでないのでポジショントーク気味です)

topcoder は int, long long, string とそれらの配列 (vector) のみです． IOI (2010-) も関数形式で，それらとさらに 2 次元配列も使われています． IOI は (手元テスト用の) ファイル入力の形式も指示されていて，特定の配列が縦に並んでいることも横に並んでいることもあります． pair 等を使わないのは多言語対応という側面もありそうです．

使う型は少なくしておいた方がよさそうという意見と，与えられる変数をその変数名通りに与えるのがわかりやすいんじゃないかなぁという意見です (ファイル入力の構造よりも数学的記法の構造を重視という感じ)．

[KentaroMatsushita]

vector 複数個派です。 タプルにすると名前を毎回考えたり、順番を考えたりするのが面倒そうですし、そもそもコード内ではほとんどの人が一旦それぞれの vector に直すことも多そうなので tuple にしても誰も嬉しくないかなとは思います。

[yosupo06]

vector派です　本来の入力の構造をそのまま保つのが一番混乱が少ないと思います　利便性の観点だと、「自分がストレステストかなにかでsolve関数を用意したくなったときの形式」が一番楽だと思っていて、これも私だったらvectorなんですがここは意見が分かれそうです

あとこういうクエリごとに形式が違うタイプの問題とかだと https://judge.yosupo.jp/problem/point_set_range_sort_range_composite 引数がすごい数になりそうで、個人的に引数がすごい数の関数が好みではないというのもあります

[yosupo06]

vector<pair>やvector<tuple>については、vectorに勝っている点があまりわかっていないです

[KentaroMatsushita]

ふと思ったんですが、クエリのタイプによって引数の数が違う問題はどうするべきですかね、それに合わせて形式を統一化するのはアリかもと思いました(query_type の方が使わない変数があっても不自然じゃないかなとは少し思いました)

[noshi91]

例えば

0 a b
1 l r x

という 2 種類のクエリがあるなら

struct query_type {
  int type, a, b, l, r;
  long long x;
};

みたいにするのが 1 つの案ですね。後は

struct query_type0 {
  int a, b;
};
struct query_type1 {
  int l, r;
  long long x;
};

として std::variant<query_type0, query_type1> を使う案もありますが

[maspypy]

これは結局、クエリ形式について結論が出ないまま作業ストップしている状態ですか？ @noshi91

[GoatGirl98]

$f(x)=ax+b\to f^{-1}(x)=\cfrac{1}{a}x-\cfrac{b}{a}$ 。So this operation has an inverse under modulo $998,244,353$ 。I was wondering if setting an extra problem and change $998,244,353$ into arbitrary modulo would be better for verifying Disjoint Sparse Table ?

[maspypy]

You can verify DST with mod 998244353 version, also with https://judge.yosupo.jp/problem/staticrmq.

[maspypy]

struct query_type0 {
  int a, b;
};
struct query_type1 {
  int l, r;
  long long x;
};

として std::variant<query_type0, query_type1> を使う案もありますが

これでおねがいします