0w1

Segment Tree

SOJ 86. 一維陣列區間加值區間乘值區間查詢總和

Problem Description: Initially, you are given an array of length N. Q operations follow: OP 1: Add C to every element in X..Y OP 2: Multiply by W on every element in X..Y OP 3: Output the sum of elements in X..Y, modulo 1e9 + 7Constraints:…

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 ]…

ARC 074 D - 3N Numbers ( Segment Tree )

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder題意: 給長度 3 * N 的數列 A[]。刪除 N 個元素後,希望前 N 個元素總和 - 後 N 個元素總和最大。制約: N ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法: 考慮一條線,從 N 掃描到 2 * N。 這條線會將數列分成兩塊,…

CFR 788 E. New task ( Segment Tree, Fenwick Tree )

Problem - 788E - Codeforces題意: 給長度 N 的數列 A[]。 這個數列代表士兵們,他們的強度。初始時所有士兵都是活著的。一個隊伍是合法的,如果他有 5 個人,令下標為 a 有 M 筆詢問,分為兩種: 1 x:反轉 x 號士兵的狀態 ( 保證活 -> 死 ) 2 x:反轉 x …

CFR 794 F. Leha and security system ( Segment Tree )

標ㄐㄧProblem - 794F - Codeforces題意: 給長度 N 的數列 A。有 Q 筆詢問,分兩種: 1 l r x y:代表要將 A[ l .. r ] 中所有 x 的數位變換成 y 2 l r:代表要輸出 A[ l .. r ] 的總和制約: N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9 For query type 1: y != 0解法: …

CFR 799 C. Fountains ( Segment Tree )

Problem - C - Codeforces題意: 有 N 樣物品,用價格和價值描述。一樣物品可能是要用 C 類貨幣購買,也有可能是要用 D 類貨幣購買。選兩個相異的物品購買,使得價值總和最大。輸出價值總和。制約: The first line contains three integers n, c and d (2 ≤…

CFR 806 E. Blog Post Rating ( Segment Tree, Fenwick Tree )

Problem - E - Codeforces りんごさんの提出見て回答。題意: 有 N 個人,編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數,輪到他的時候他會依據當前的票數,操作使得接近他的期望票數。求對於所有 x,編…

CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )

Problem - 609F - Codeforces題意: 有 N 隻青蛙在一維數線上,用位置和舌頭長度描述。現在依序有 M 隻蚊子出現,用位置和營養值描述。一個在位置 x,舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t,而且這隻青蛙是所有能吃到這隻蚊子的…

HE XOR queries ( Persistent Segment Tree on BIT, XOR, Online, Kth )

XOR queries | Segment Trees & Data Structures Practice Problems | HackerEarth題意: 給一個數列 A。要求在線處理 Q 筆詢問: 第一種: __將 A[ i ] 改為 x 第二種: __問 A[ l, r ] 排序後,其中 [ i, j ] 間的 xor 值為何。制約: N, Q ≤ 5e4 1 ≤ A[ i…

ARC 073 F - Many Moves ( DP, Segment Tree )

F: Many Moves - AtCoder Regular Contest 073 | AtCoder題意: 在一個一維的棋盤上,你有兩顆棋,一顆在 A 位置,另一顆在 B 位置。有 Q 次操作,第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後,可…

CFR 803 G. Periodic RMQ Problem ( Discretization, Segment Tree )

Problem - G - Codeforces題意: 給一個長度為 n 的 B 數列。現在將 B 數列黏貼 k 次變成一個新的數列。有 Q 筆詢問: op = 1: __將 [ l, r ] 中的元素全部更改為 x op = 2: __詢問 [ l, r ] 中的最小值制約: The first line contains two integers n and k…

CSAcademy 25. Min Ends Subsequence ( Persistent Segment Tree )

Round #25 (Div. 2 only)題意: 給一個排列 1 ~ N,問最長的一個子序列,滿足:頭尾元素都比所有中間的元素大。輸出長度。制約: 1 ≤ N ≤ 1e5解法: 不失一般性,假設最長的這個子序列的頭 i 和尾 j 滿足:i 枚舉所有 i,令 j 為 i 顯然這個 j 是最優的,而…

CFR 786 B. Legacy ( Dijkstra, Segment Tree )

Problem - B - Codeforces題意: 給一張圖,N 個點,Q 個邊,起點 S。 邊有三種,各自用 u, v / L, R, w 描述: 1. u -> v : 代價 w 2. u -> [ L, R ] : 代價 w 3. [ L, R ] -> u : 代價 w 問所有終點的單源最短路徑,不存在則輸出 -1。資料規模: N, Q ≤ 1e…

TIOJ 1952 小向的試煉 3-3:鑰匙 ( Segment Tree, Tags )

1952 - 小向的試煉 3-3:鑰匙(Key) | TIOJ INFOR Online Judge題意: 給一個長度為 N 的字串,接著 M 筆詢問。詢問 L, R, K 代表 [ L, R ] 的字母要按照字典序大到小( K = 0 ) 或小到大( K = 1 )排序。求所有操作後的字串長相。資料規模: 第一行有兩個正整…

HDU 1542 Atlantis ( Scanning Line, Segment Tree )

Problem - 1542題意: 給很多矩形的左下角和右上角座標,問聯集面積為何。資料規模: 座標為有理數 N ≤ 100解法: 離散化座標後,由下到上推移掃描線。時間 / 空間複雜度: O( N lg^2 N ) / O( N lg N ) #include <bits/stdc++.h> using namespace std; const int MAXN = 10</bits/stdc++.h>…

IOI 1998 Picture ( Scanning Line, Segment Tree )

PEG Judge - IOI '98 - Picture題意: 給很多矩形的左下角和右上角座標,問總周長為何。被包含的線段不算在周長裡。資料規模: The first line of the input contains the number of rectangles (0 ≤ number of rectangles 解法: 掃描線,考慮對 X, Y 方向…

POI 21 Stage 1 Couriers ( Persistent Segment Tree )

http://main.edu.pl/en/archive/oi/21/kur題意: 給一個長度 N 的數列,接著 M 筆詢問 [ L, R ] 中是否有個數字是絕對多數,有的話輸出該數字。資料規模: N, M ≤ 5e5 1 ≤ P ≤ N TL: 12000 ms ML: 128 MB解法: 一個持久化裸題,但記憶體卡得比較緊,要用離…

CFR 589 G. Hiring ( Segment Tree, Binary Search )

Problem - G - Codeforces題意: 給 M 個工作時間,N 個人的特徵 D[ i ] 與 R[ i ],代表第 i 個人在一天工作時,需要前 D[ i ] 單位時間預熱,然後才能開始算入工作時數,而每一天的工作時數總和起來需要 R[ i ]。問分別每個人會在第幾天做完他的作業,做不…

IOICJ 36 Interval Sum EX ( Math, Segment Tree )

Problem Description: You are given an array A wit length N. You need to support these operations, noted with [ p, e, c ]: if p = 0: __square root and discard non-integer value of range [ e, c ] if p = 1: __change value at e to c if p = 2: …

CFR 380 C. Sereja and Brackets ( Segment Tree, D&C, Bracket Sequence )

Problem - 380C - Codeforces題意: 給一個括弧序列,和若干筆詢問。詢問給 L, R,問原序列的 [ L, R ] 區間裡最常的合法匹配序列 ( 可間斷 ) 多長 。資料規模: 序列長度 ≤ 1e6 詢問數 ≤ 1e5解法: 考慮基於分治的預處理。如果我們知道一個區間分別的最長合…

Yuki 318 学学学学学 ( Ad hoc / Segment Tree )

No.318 学学学学学 - yukicoder題意: 給一個數列 A。現在要產生另一個數列 B。產生的步驟為: for each integer t in 1 to 1e9: __for each integer x in leftmostPositionInA( t ) to rightmostPositionInA( t ): ____B[ x ] = t 求 B 的最終樣貌資料規模…

HE April Circuits 3B - Bear and Special Dfs ( Timestamp + Segment Tree + Modular Inverse )

https://www.hackerearth.com/april-circuits/algorithm/utkarsh-and-special-dfs/ Modifying some node u, changing a[ u ] to some new value x, the vis count of each node of subtree of u will be divided by the original a[ u ], and multiplied by …

CFR 337 D. Vika and Segments ( = 矩形面積 Segment Tree + Scanning Line )

Problem - D - Codeforces 事實上應該有更好的解法,就是先把所有矩形的面積取和,再用BIT之類的結構維護一些東西,計算所有重疊的部分然後減去。但顯然也能直接當作是矩形面積覆蓋問題。因為後者比較有實用性,而且自己不太熟悉,我試著實現了後者。這是一…

CFR Educational 10 D. Nested Segments ( Segment Tree + Scanning Line )

Problem - D - Codeforces Sort by left bound, that scan from left to right, we will query the number of right bounds that are before the right bound of the current segment. After answering the query, the segment should be removed, which wil…

CFR 602 D. Lipshitz Sequence ( Segment Tree )

Problem - D - Codeforces It is well known fact that only the adjacent elements would have the maximum slope. Making use of this fact, we can always find the maximum slope, find all subsequences it will contribute to, then apply divide and …

IOI 15 Horses ( Segment Tree )

終於做出來了。。 首先要直覺地想到,如果有一個日期是值得賣的,那麼一定會將所有都在這一天賣出去,因為如果留到後面的價值更高,這一天就根本不會是值得賣的。 如果要比較兩個不同日期賣出的錢,舉例來說比較 day i 和 day j,且不失一般性 i x[ 1 ] * x[…

CFR 622 C. Not Equal on a Segment ( TLE Mo's / AC Segment Tree )

Problem - C - Codeforces すぐに思いついたのが mo'sだったが、実装が下手すぎてTLEした。 でも自分の書き方のバグに気付いた。 以前は int lb = 2, rb = 1; みたいなもの書いてすぐ適当に尺取りしていたが、 もしさきに lbを縮ませてしまうとまだ何も入っ…

IOI 15 Teams ( Persistent Segment Tree + Stack Monotonicity )

PEG Judge - IOI '15 - Teams 就是一個蛋疼。。改天補說明。 這個問題有兩種解法,一種是霍爾定理+DP,似乎code比較短也比較好寫,但我對二分匹配完全沒概念Orz。。 只能用持久化線段樹去很直觀的搞,雖然說這就是想定解。 首先因為每個學生的屬性是二維的,…

UVA 11297 Census ( 2D Segment Tree Single Point Modify )

UVa Online Judge 之前的寫法是錯的 每一個二維結構存的應該是一個 x軸的線段樹,每一個節點保有該二維的上下界範圍內所有 y的 min / max。但我之前只是隨便更新而已,變成只要O( lg n ),但如果同個節點被修改兩次就會發生問題,因為包含自己的二維結構不會…