0w1

Entries from 2017-06-05 to 1 day

CFR 444 C. DZY Loves Colors ( Segment Tree, Dummy Constraints )

Problem - 444C - Codeforces題意: 給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。 M 筆詢問,兩種形式: 1 l r x:將 [ l, r ] 都塗色為 x 2 l r:輸出 [ l, r ] 的貢獻總和 初始時所有元素的貢獻為 0。 當一個元素由 u 變為 v 時,增加貢…

CFR 522 D. Closest Equals ( Segment Tree )

Problem - 522D - Codeforces題意: 給你長度 N 的數列 A[]。 M 筆詢問,問 [ L, R ] 中,最近的相同元素距離是多少。若不存在,輸出 -1。制約: 1 ≤ N, M ≤ 5e5 abs( A[ i ] ) ≤ 1e9解法: 可以很快想到,給每一個位置 i 紀錄前一個 A[ i ] 的位置 pre[ i ]…

CFR 556 D. Restructuring Company ( Union Find )

Problem - 566D - Codeforces題意: 給你 N 個人,初始時他們自己一個組。 Q 筆詢問,三種形式: 1 x y:merge( x, y ) 2 x y:merge( x, x + 1, ..., y ) 3 x y:print "YES" if group( x ) == group( y ) else "NO"制約: 1 ≤ N ≤ 2e5 1 ≤ Q ≤ 5e5解法: …