【クエリメニュー】区間和 (paizaランク C)-解答例-PHP編

2022年8月30日

【クエリメニュー】> 【平方分割】STEP: 2 区間和 (paizaランク C 相当) [難易度: 1569 ±27]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

長さ N の数列 A と、K 個の区間 (l_1,r_1) ... (l_K,r_K) が与えられるので、各区間についての A の区間和 A_{l_i} + ... + A_{r_i} (1 ≦ i ≦ K) を求めてください。

入力値（例）
4 2
16
88
10
-65
2 4
1 2

出力値（例）
33
104

解答例

<?php
    list($n, $k) = explode(" ", trim(fgets(STDIN)));
    
    $ans[] = 0;
    
    for ($i = 1; $i <= $n; $i++) {
        $a[$i] = trim(fgets(STDIN));
        
        if ($i == 1) {
            $ans[$i] = $a[$i];
        } else {
            $ans[$i] = $ans[$i-1] + $a[$i];
        }
    }
    
    //print_r($ans);
    
    for ($i = 0; $i < $k; $i++) {
        list($k1, $k2) = explode(" ", trim(fgets(STDIN)));
        
        $result = $ans[$k2] - $ans[$k1-1];
        echo $result. "\n";
    }
?>

<?php

list($n, $k) = explode(" ", trim(fgets(STDIN)));

$ans[] = 0;

for ($i = 1; $i <= $n; $i++) {

$a[$i] = trim(fgets(STDIN));

if ($i == 1) {

$ans[$i] = $a[$i];

} else {

$ans[$i] = $ans[$i-1] + $a[$i];

}

//print_r($ans);

for ($i = 0; $i < $k; $i++) {

list($k1, $k2) = explode(" ", trim(fgets(STDIN)));

$result = $ans[$k2] - $ans[$k1-1];

echo $result. "\n";

}

解説

この問題も累積和と同じように、受け取った整数aを先に計算しておきます。

ans[0]	0	0
ans[1]	16	16
ans[2]	88	ans[2-1](16)+a[2](88)=104
ans[3]	10	ans[3-1](104)+a[3](10)=114
ans[4]	-65	ans[4-1](114)+a[4](-65)=49

次に受け取った整数k1とk2を計算（ans[k2]-ans[k1-1])して出力します。

入力値（例）でいえば、
4 2は、ans[4](49)-ans[1](16)=33
1 2は、ans[2](104)-ans[0](0)=104
となります。

解答例

解説

カテゴリー