コンテスト中に解けなくて、SparseTableを使ってupsolveした！ら、kmjpさんのsubmitをみて確かにそれはそうだ...となった解。 (それまでにあり得るminをとるということで)アプローチは同じなのだけど、データ構造で殴って思考停止になるのはダメ・ゼッタイと思いました。
題意
問題では写真撮影とされていますが、同じ意味を長方形で示します。
- n個 ($1 \leq n \leq 10^5$)の長方形(正方形かもしれない)があります。縦横を$h,w$($1 \leq n \leq 10^9$)とします。それぞれ、$a_1, a_2 ... a_n$として区別します。
- 各長方形について、それよりも完全に小さい長方形が存在すればそのindexを述べ、存在しなければ-1を出力してください。(つまり、縦か横が"同じではだめ"です。)
- 各長方形は縦横を入れ替えてもよいです。
- 複数の候補がある場合、どれを答えてもよいです。
例
- 「サンプル1」1."3x4", 2"5x4, 3."3x3"があった時、2だけは3よりも大きいです。1はwだけ3よりも大きいですが、hが同じため要件を満たしません。3は1,2を隠すことはできません。[-1, 3, -1]を出力します。
- 「サンプル」1. 3x6, 2. 4x2があった時、2はひっくり返すと、2x4として扱えます。このため、1にとって2は小さい長方形です。[2, 1]を出力します。
- 「サンプル」1. 3x3, 2. 3x3があった時、同じ長方形は小さいと呼べないので[-1, -1]です。
問題の言い換え
- n個の点があります。それぞれの座標は$x, y$ (ただし、$1 \leq x \le y \leq 10^9$)です。それぞれの点を$a_1, a_2 ... a_n$とします。
- 各点について、その点よりも左下の座標に点があればそのindexを答えてください。そのような点がない場合は-1を答えてください。
元の題意を考えて、各紙の1点を原点に合わせて$x,y$軸に沿って第一象限に置くとすると、$h,w$を$x,y$として扱ってよいです。それぞれの紙は回転させて良いので、$x \leq y$となるように置いて考えます。(図中青字の「回転」)この時、完全に小さい紙とは、より左下にある点(の紙)であることは明らかです。
考え方1: xを小さい方から見ていく
今、$x$が小さい方からすべての点を見ていくとします。ある程度の点を見た後に、点$a,b$より小さい紙(左下の点)$c,d$を見つけたいとします。
- この時、$c$は$a$よりも小さい点であることが必要です。これは、$x$を小さい方から見ているため、すべて走査済みです。ただし、いままで見てきたすべての点には、$x=a$の点も含まれるので、それらを含めてはいけません。(ちょうど$x$の幅は重なってしまうので答えになりません)
- $c < a$であるならばその中で高さがbよりも低い点はすべて解になり得ます。つまり、これまでの高さの$min$をとっていればそれが存在するかを確認できます。
上の図で今、紫の点より左下の点を探したいとします。まず、xがより小さい点(頭上はほかのすべての点)が候補になり得ます。このxの点たちを確認するまでのmin(図では赤)が紫の点より低いなら、それは答えです。
もしも、紫の点がこれまでに見てきた点のminと同じか低いなら、答えは存在しません。
import sys
input = sys.stdin.readline
def do():
import collections
n = int(input())
m = collections.defaultdict(list)
data = []
datb = []
for i in range(n):
a, b = map(int, input().split())
a, b = min(a,b), max(a,b) #x軸方向を小さい数字にする
data.append(a)
datb.append(b)
m[a].append(i) # 各xの値毎にindex(点)をリストで保存する ための辞書
mi = 2 ** 60 # 初期値。最初のx in klのループでは答えは存在しない
ret = -1
r = [0] * n # 結果
kl = list(m.keys()) # xを小さい方から見たいので、辞書のキーを小さい方から見ていく
kl.sort()
# このループでxが小さい座標から見ていく
for x in kl:
# ループ1回目。これは１つ前のxのループまでのminの比較
for ind in m[x]: # indはそのx座標にいる点のindex
if mi < datb[ind]: # もし、その点のy座標がこれまでのxのmin(y)より高いなら
r[ind] = ret # 答えは存在する
else:
r[ind] = -1 # そうでないなら答えは存在しえない
# ループ2回目。これは「そのxを含めて」最小のmin(y)を計算する
for ind in m[x]:
if datb[ind] < mi:
mi = datb[ind]
ret = ind + 1 # そのindexを答えように保存
print(" ".join(list(map(str, r))))
q = int(input())
for _ in range(q):
do()
考え方2: SparseTable
この問題を愚直に考えると
$h$ x $w$の紙があった時、$h-1$までのすべての紙の中で最小の幅が$w-1$ならそれが答えです。つまり、minの値とindexを一緒に返せるRMQ(min)が行えればよいです。(h,wをひっくり返して試行します)。ただし、$1 \leq n \leq 10^9$なので、座標圧縮が必要です。
わざわざ考え方2と書いておいてなんですが、「一辺よりも小さい点の中で、もう一辺がより小さいminと比べる」というアプローチは考え方1と同じです。考え方1では、各エントリ(=xごとの点)を順番に見ていき、1つ小さいxまでのminを保持しながら解を求めており賢いです。
class sparseTable(object):
func = min
def __init__(self):
self.table = []
self.depthTreeList = 0
def load(self, l):
self.n = len(l)
self.depthTreeList = (self.n - 1).bit_length() # Level
self.table.append(l)
for curLevel in range(1, self.depthTreeList):
l = []
for i in range(self.n - (2 ** curLevel - 1)):
n1 = self.table[curLevel - 1][i]
n2 = self.table[curLevel - 1][i + (2 ** (curLevel - 1))]
if n1[0] < n2[0]:
l.append(n1)
else:
l.append(n2)
self.table.append(l)
def query(self, l, r): # [l, r)
diff = r - l
if diff <= 0:
raise
if diff == 1:
return self.table[0][l]
level = (diff - 1).bit_length() - 1
n1 = self.table[level][l]
n2 = self.table[level][r - (2 ** level)]
if n1[0] < n2[0]:
return n1
else:
return n2
def do():
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
n = int(input())
dat = []
INF = 2**60
zatsu = set()
for i in range(n):
num = i + 1
a, b = map(int, input().split())
a,b = min(a,b), max(a,b)
zatsu.add(a)
zatsu.add(b)
dat.append([a, b, num])
if n == 1:
print("-1")
return
# 座標圧縮
zatsu = list(zatsu)
zatsu.sort()
zatsu = list(enumerate(zatsu))
zTable = dict()
for i in range(len(zatsu)):
zTable[zatsu[i][1]] = zatsu[i][0]
sList = [[INF, -1] for i in range( len(zatsu))]
# 座標圧縮に点を対応させるとともに、Sparse Tableに乗せるテーブルを作る
for i in range(n):
a,b,num = dat[i]
a,b = zTable[a], zTable[b]
dat[i][0] = a
dat[i][1] = b
if sList[a][0] > b:
sList[a] = [b, num]
if sList[b][0] > a:
sList[b] = [a, num]
st = sparseTable()
st.load(sList)
res = []
# w, hを総当たりで、-1までの区間にもう一方より小さい点があるかを確認
# あるなら、そのindexを答えとする
for i in range(n):
a,b,num = dat[i]
xres = -1
if a > 0:
x = st.query(0, a)
if x[0] != INF and x[0] < b:
xres = x[1]
if b > 0:
x = st.query(0, b)
if x[0] != INF and x[0] < a:
xres = x[1]
res.append(xres)
print(" ".join(list(map(str, res))))
q = int(input())
for _ in range(q):
do()