Subscribed unsubscribe Subscribe Subscribe

0w1

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 ),但如果同個節點被修改兩次就會發生問題,因為包含自己的二維結構不會…

JOI 14 予選 Treasures ( MLE Discretized Segment Tree )

Treasures | Aizu Online Judge It's easy to see that we will have to split them into two equal size sets and update the answer for each set to set. Since there are three options for each item, we will have to enumerate all 3 ^ |s| possible …

POJ 2019 Cornfields ( 2D Segment Tree )

2019 -- Cornfields ふぁぁ、初めての二次元セグメント木AC。楽しかったです。でも僕はポインタの書き方にしかなれないから、メモリを静態に宣告しなければTLEしてしまいます。でもMAXMEMをちゃんと十分( RE )で多すぎない( MLE ) ように工夫するのは難しい…

AOJ 1068 School of Killifish ( STILL MLE 2D Segment Tree )

School of Killifish | Aizu Online Judge 二次元セグメント木をやるだけ、だと聞きました。でも当たり前にMLEしました。O( n * ( lg ^ 2 ) n ) で n ≤ 1e6。諦めますが、初めての二次元セグメント木で、色々勉強になったので一応MLEしたコードでも載せます…

CFR 101 B. Buses ( DP + Segment Tree )

Problem - 101B - Codeforces dp[ i ][ t[ i ] ] = sum{ dp[ i - 1 ][ s[ i ] .. t[ i ] - 1 ] }, Ɐ i: current bus bus需要先依據終點 t做昇序排序。 注意因為區間範圍可能很大,所以需要離散化。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9</bits/stdc++.h>…

CFR 52 C. Circular RMQ ( Segment Tree )

Problem - 52C - Codeforces Tag のちょっとした練習になる。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXM = 2e5 + 5; const int MAXABSV = 1e6 + 6; typedef long long ll; const ll INF = 1e16; int n; int a[ MAXN ]; int </bits/stdc++.h>…

AOJ 2431 House Moving ( DP + Segment Tree )

House Moving | Aizu Online Judge JOI 11 Day4 Bookshelf ( DP + Segment Tree ) - 0w1 とほぼ同じ。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; #define int long long struct itvt{ int maxv; int lb, rb; itvt *lc, *rc; itvt(int _l = </bits/stdc++.h>…

JOI 11 Day4 Bookshelf ( DP + Segment Tree )

Bookshelf(本棚) - joi2011-day4 - 情報オリンピック 問題と解説 bookshelf: 本棚 (Bookshelf) - 2011年 日本情報オリンピック春合宿OJ | AtCoder 「この本を動かすかどうか」を直接決めるのはできなさそう。なのでDPを考えてみる。しかし「今の本を動かす」…

JOI 10 本選 Bug Party ( Binary Search + MLE Persistent Segment Tree / AC Priority Queue )

Bug Party | Aizu Online Judge 很容易想到,如果固定最小值b,那麼我們必須由小到大拿進所有a,直到 sum( a ) ≤ b * cnt 不再成立。由於要快速( O( lg n ) 以下 ) 求出大於等於某個b值的最小的x個a值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…

JOI 11 本選 Night Market ( 区間DP )

Night Market | Aizu Online Judge ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをす…

ABC 32 C - 列 ( Crawling / log() / Segment Tree )

C: 列 - AtCoder Beginner Contest 032 | AtCoder Crawling. O( n ). #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e9 + 9; typedef long long ll; int n, k; int s[ MAXN ]; void solve(){ if( count( s, s + n, 0 ) ){ pr</bits/stdc++.h>…

ABC 17 C - ハイスコア ( Imosu or Segment Tree )

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder Basically we would like to find the element that is covered with the least cost. It is intuitive to use segment tree, but actually we could use imosu algorithm to maintain the differen…

Persistent segment tree

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…

Range Mex

Mex ( minimum excludant ), has an interesting property in game theory, where an sprague grundy value of a state in a fair game can be deduced from the mex of the sg-values of all the states it could reach in the next step.The definition of…