Atcoder Express2

Atcoder Python

今回はソースコードだけ（コード内にメモ用解説があります）

N,M,Q=map(int,input().split())
 
 
 
answer=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  answer[N-L][R-1]+=1
 
for i in range(1,N):
  answer[0][i]+=answer[0][i-1]
  answer[i][0]+=answer[i-1][0]
  
print(answer[0])
for i in range(1,N):
  for j in range(1,N):
    answer[i][j]+=answer[i-1][j]
    answer[i][j]+=answer[i][j-1]
    answer[i][j]-=answer[i-1][j-1]
for i in range(Q):
  p,q=map(int,input().split())
  print(answer[N-p][q-1])
 
'''
#図のような正方形で累積和を考える
こう取ればLが1でRが10の時（一番右下の時)全ての区間が入るように和を計算できる
 
  1 2 3 4 5 6 7 8 9 10 ←R
10                   1
9
8
7                 1
6           1 1
5               1
4         1   2
3
2                 1
1           1
↑
L
 
例えば、L,R=5,8の電車はもちろん5,8の区間に含まれている。
ここで5,8の区間に含まれる電車の数を考えると5,7の電車や6,8の電車は含まれている...
という風に考えると累積和を取れる
ここで、6,7の区間に含まれる電車の数は5,7と6,8を数えることで2回計算されているのでマイナスする
 
 
'''