の続きです

D問題
- 解法
  - 解法1
  - 解法2

D問題

D - AtCoder Express 2

横1列に並ぶN個の町を結ぶM(<=100,000)本の路線のうち、「LからRに完全に含まれる路線の数を求める」というクエリにQ問答えるという問題です。

解法

解法が2つありますが、どちらも、「路線の区間(l, r), 質問の範囲(L,R)を二次元座標で考える」という発想が必要です。
どういうことかというと、このような問題があったら(atcoderのサンプル2です)(路線の区間を(l, r)、質問の範囲を(L, R)とおく)

$N=10, M=3, Q=2$
$l_1=1, r_1=5$
$l_2=2, r_2=8$
$l_3=7, r_3=10$
$L_1=1, R_1=7$
$L_2=3, R_2=10$

f:id:tako0608:20180819154912p:plain

これから、

f:id:tako0608:20180819152627p:plain

こうするという事です。2番目のクエリについてみてみると、

f:id:tako0608:20180819153227p:plain

このようになり、問題は「この表でたてよこそれぞれL-1からRまでに含まれる路線の数を数える問題にQ個答える」と言い換えられます。
(上の例だと答えは 1 1)

数える方法を2つ紹介します。
実際に数えるのを実装するよりも、ここまで説明した問題の言いかえの部分の方が114514倍難しい気がします...

解法1

累積和(そこまでに何個あるか)を使い、数える部分を分割して足します。簡単です。
横の行ごとに累積和をとった図で言えば、(オレンジ $-$ 黄色)が答えになります。累積和を求めるのに $O(N^2)$ 、各クエリについて $O(N)$ で解けるので、この解法は $O(N^2+QN)$ です。

#include "bits/stdc++.h"
using namespace std;
int s[510][510];
int main(){
    int n,m,q;cin>>n>>m>>q;
    int l,r;
    for (int i=0; i<m; ++i){
        cin>>l>>r;
        for (int j=r; j<=500; ++j)++s[l][j];//累積和は後にふつうに求めたほうがいいかもしれないです。今回はどちらでも余裕
    }
    int ans;
    for (int i=0; i<q; ++i){
        cin>>l>>r;
        ans=0;
        for (int j=l; j<=r; ++j)
            ans+=s[j][r]-s[j][l-1];
        cout<<ans<<endl;
    }
}

解法2

二次元累積和を使います。二次元累積和の説明を先にします。
普通の累積和
$a_i$ に対して累積和 $S_i$ は、0からiまでにあるaの和を表します。
これをすると何がいいかというと、pからqまでにあるaの和を、 $S_q-S_{p-1}$ で $O(1)$ で求めることができることです。
$S_i$ の求め方は、 $i=1$ から見て行って、s[i]=s[i-1]+a[i-1]と計算していけば求まります。
これを使ったのが解法1です。
二次元累積和
同様に、 $a_{i,j}$ に対して累積和 $S_{i,j}$ は、0からi, jまでにあるaの和を表します。i, jまでとは、 $i=5,j=9$ のときこういうことです。
この表をよく見ればわかりますが、しっかり(i, j)までの値の和になっています。
普通の累積和と同じように、求め方と、使い方を知りたいのですが、その前にこれを見てください。 ...①
これを変形すると ...②
$S_{i,j}$ を求めるには、②を使います。赤い部分が $a_{i,j}$ の1マスだと考えます。
求め方： ②より、 $S_{i,j}=a_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}$ ですから、 i, jを1から見て行って、 s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1] を計算して行けば出来上がりです。
これをすると何がいいかというと、範囲内の $a_{i,j}$ の和を $O(1)$ で求められます。
範囲内の $a_{i,j}$ の和を求めるには、①を使います。赤い部分が求めたい範囲だと考えます。
求め方： ①より、求めたい範囲を(pl,ql)から(pr,qr)とすると、 $(範囲内のaの要素の和)=S_{pr,qr}-S_{pl-1,qr}-S_{pr,ql-1}+S_{pl-1,ql-1}$ ですから、s[pr][qr]-s[pr][ql-1]-s[pl-1][qr]+s[pl-1][ql-1]が答えです。
▽下の表で、みどりで囲った範囲の中にある $a$ の要素の和は, $3 - 1 - 1 + 1 = 2$ で、合っています。

D問題に二次元累積和を使ってみる

これを知っていれば、数える部分はやるだけになるのかもしれません。
数えるのが $O(1)$ ですので、全体で $O(N^2+Q)$ です
この問題では二次元累積和である必要がありませんでしたが、応用ができそうな技術ですので覚えておきたいです。
実装例:

#include "bits/stdc++.h"
using namespace std;
int s[510][510];
int main(){
    int n,m,q;cin>>n>>m>>q;
    int l,r;
    for (int i=0; i<m; ++i){
        cin>>l>>r;
        ++s[l][r];
    }
    for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    for (int i=0; i<q; ++i){
        cin>>l>>r;
        cout<<s[r][r]-s[r][l-1]-s[l-1][r]+s[l-1][l-1]<<endl;
    }
}