ABC106
全完できました！！
AtCoder Beginner Contest 106 - AtCoder
小学校で見たことがある気がする長方形の面積から道路の面積を引く問題
今回なら(縦の長さ)*(横の長さ)-(縦の長さ＋横の長さ)+1となります
１からNまでの中で奇数かつ約数を８つのみ持つ数を求める問題
これも１からNまで１個ずつ奇数かどうか、約数を何個持つかを丁寧に調べれば出ます
最初に数字のみの文字列が与えられて1日経つごとに1→1,2→22,3→333のようにn→（nがn個）と文字列が変形していく問題。
5000兆日後は例え最初の文字列が2だろうとk(≦10^18)文字目は2になるので最初の時点でK文字目まで1が並んでいるなら1,それ以外の場合なら頭から見て最初にある1以外の数が答えになります
一直線上に並んだN(≦500)個の都市の任意の都市Li,Ri(Li≦Ri)を結ぶ列車がM(≦200000)本あり
高橋くんのQ(100000)個の質問,都市pi,qi間に区間が完全に含まれる列車の本数は何本かにそれぞれ答える問題
M,Qがそれなりに大きい数なので各都市i,jについて素直に調べるとTLEしてしまいます(少なくともO(N^2*M)?)
そこで都市i,j間に区間が完全に含まれる列車の数をans[i][j]とするとans[i][j-1]にRi==jかつLi≧iとなる列車の本数を足したものがans[i][j]になります
(追記)(自分でも通しました)もっと早い方法があるっぽい・・・
都市i,j間に区間が完全に含まれる列車の数をsum[i][j]にして
sum[Li][Ri]を各iについて+1して
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]となり
クエリL,Rに対して
ans=sum[R][R]-sum[L-1][R]-sum[R][L-1]+sum[L-1][L-1]となるようです
sum[i][j]を[1≦i][1≦j]区間での累積和として[L≦i][j≦R]区間になるようにansに入れ直してます
