https://www.acmicpc.net/problem/2517
時間2秒、メモリ192 MB
input :

N (1 ≤ N ≤ 500,000)

3行のうち、各試験の1位からN位までの学生

output :

「もう起きられない」学生数

条件:

助教は試験のたびに成績を同数の学生が一人もいないと決めた.

Aの学生がBの学生より3回の試験で成績がよかったら、AはBの「すごい」

Cより「起きられない」学生が一人もいなければ、Cは「起きられない」.

まず難しく、フィンウィックの木を利用して最高価格の方法を探すことを学ぶきっかけになった.
最高価格の方法を探す
同じ内容の論文から説明を始めたようです.
基本的なフィンウィックツリーでは、配列内の要素を追加し続けて区間和を求めることができますが、異なる方法で最適値を格納することもできます.
特定の区間内の最大値を探すには、2つのツリーを使用して重複しない区間を検索し、1つの要素は個別に格納された方法を使用します.

解析

まずフィンウィックの木を置いて、問題のアイデアを考えてみましょう.
「すごい」学生の数を探してみましょう.すごい学生は何ですか.
Cより強い学生が一人もいなければいい.
つまり、CはXよりCのほうがいいということです.
逆に、Cよりいい子がいないと、「できない」子になります.
基本的に、1位を獲得した学生は、自分ほど苦手な学生はいないと考えることができ、例題の「5」番の学生など、他の場合もあります.
したがって、例では、答えは基本1位+「5」番の学生=4です.
でもこう見るとどうやって解けばいいかわからない
どう比較すればいいか分かりません.
まず基本的に1回目の試験の場合は、ソートでリストできます.
これで簡単に自分よりいい試験を受けた人を前に送ることができます.
残りの2つの試験を比較して、フィンウィックの木に合格して表示する必要があります.

木。

ソートでリストされているので、残りの2つの数字(試験結果)をどのように利用するかを考えます.
これに対する考え方は,インデックス,価値によって表される.[1~2次試験の点数]までの区間で一番点数が高い人を見つけて、「3次試験の点数」を下回ると、「取れない」学生がいます.
このようにして、ツリーに「inf」値を格納し、for文で各学生のレベルを格納します.
ここで見る区間は固定[1-2番目の等号]なので、元のフィンウィックツリーでも完全に検索できます.
デフォルトではupdateを行うとidx+=(idx&-idx)が実行され、これらの値の最高値に更新されるため、すばやくナビゲートできます.
そして、戻り値(3回目の試験で一番よかった学生の点数)を自分の点数よりも、自分の点数が高ければ、「出来ない」学生なので正解+=1です.

import sys


def update(idx, val):
    """
        idx위치의 등수를 val로 업데이트
        가장 등수가 높은 애를 저장하기 위해 min을 사용한다.
    """
    while idx <= n:
        tree[idx] = min(tree[idx], val)
        idx += (idx & -idx)


def query(end):
    """
        구간은 1 ~ end로 고정되어 있다.
        각 위치에서 최소값을 찾을 수 있도록 하면 된다.
    """
    ret = float('inf')
    while end > 0:
        ret = min(ret, tree[end])
        end -= (end & -end)

    return ret

n = int(sys.stdin.readline())
student = [[] for _ in range(n + 1)]
tree = [float('inf')] * (n + 1)

student[0] = [0, 0, 0]

for _ in range(3):
    temp = list(map(int, sys.stdin.readline().split()))

    for i in range(1, n + 1):
        num = temp[i - 1]
        student[num].append(i)

student.sort(key=lambda x:x[0])

ans = 0
for i in range(1, n + 1):
    sec_exam, thi_exam = student[i][1], student[i][2]
    former_rank = query(sec_exam)

    if former_rank > thi_exam:
        ans += 1

    update(sec_exam, thi_exam)

print(ans)