ABC343 F - Second Largest Query

atcoder.jp

問題

• 長さNの数列Aが与えられるよ
• Q個のクエリを捌いてね
  • タイプ1：$A_{i}$をxに変更
  • タイプ2：区間$l,r$の中で、2番目に大きい値の個数を出力

成約

• $1 \leq N,Q \leq 2 \times 10^{5}$

思考

• こねこねしてダメ元でSQLite投げてみたりしたけどダメでした（それはそう）
• セグ木のモノイドをイジイジする問題！教育的！
• (区間のうち1番大きい値,←の個数,区間のうち2番目に大きい値,←の個数)を乗せたら後は木が勝手にしてくれる
• セグ木って、すごい

コード

import sys
from atcoder.segtree import SegTree
input = sys.stdin.buffer.readline

N,Q = map(int,input().split())
A_L = list(map(int, input().split()))

e = (0,0,0,0)

def op(a,b):
    a_num1,a_cnt1,a_num2,a_cnt2 = a
    b_num1,b_cnt1,b_num2,b_cnt2 = b
    if a_num1 == b_num1:
        ret_num1 = a_num1
        ret_cnt1 = a_cnt1 + b_cnt1
        if a_num2 == b_num2:
            ret_num2 = a_num2
            ret_cnt2 = a_cnt2 + b_cnt2
        elif a_num2 > b_num2:
            ret_num2 = a_num2
            ret_cnt2 = a_cnt2
        else:
            ret_num2 = b_num2
            ret_cnt2 = b_cnt2
    elif a_num1 > b_num1:
        ret_num1 = a_num1
        ret_cnt1 = a_cnt1
        if a_num2 == b_num1:
            ret_num2 = a_num2
            ret_cnt2 = a_cnt2 + b_cnt1
        elif a_num2 > b_num1:
            ret_num2 = a_num2
            ret_cnt2 = a_cnt2
        else:
            ret_num2 = b_num1
            ret_cnt2 = b_cnt1
    else:
        ret_num1 = b_num1
        ret_cnt1 = b_cnt1
        if a_num1 == b_num2:
            ret_num2 = a_num1
            ret_cnt2 = a_cnt1 + b_cnt2
        elif a_num1 > b_num2:
            ret_num2 = a_num1
            ret_cnt2 = a_cnt1
        else:
            ret_num2 = b_num2
            ret_cnt2 = b_cnt2
    return ret_num1, ret_cnt1, ret_num2, ret_cnt2


seg = SegTree(op, e, [(a,1,0,0) for a in A_L])

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        p,x = query[1:]
        p -= 1
        seg.set(p,(x,1,0,0))
    else:
        l,r = query[1:]
        l-=1
        print(seg.prod(l,r)[3])