与えられた N*N 行列と、同じ与えられた行列に対する Q クエリ。各クエリの形式は x1、y1、x2、y2 です。それぞれ左上隅と右下隅として (x1,y1) と (x2,y2) で定義されるサブマトリックス内の個別の要素の数を見つける必要があります。制約: N<=300 Q<=10^5 クエリごとにサブマトリックスを反復処理する単純なアプローチを使用しています。より良いアプローチはありますか？
1 に答える
1
これは、期待できるクエリの数と、期待できる同一のクエリの数によって異なります。
1 つのアプローチは、クエリを「メモ化」して、各クエリと結果を単純に保存し、より深刻な作業を行う前にそれを調べることです。
より問題に特化したアプローチ (おそらく教師が求めているもの) は、(right,bottom)=(x,y) ごとに (0, 0, x, y) の個別の要素を計算することです。次に、各クエリを処理するのは単純な集合論です。しかし、元の計算を行うには時間がかかります。
この SO 回答への参照を忘れずに追加してください。
于 2013-12-10T06:22:07.177 に答える