0w1

Persistent

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…

HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意: 給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約: 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

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 是最優的,而…

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解法: 一個持久化裸題,但記憶體卡得比較緊,要用離…

IOI 15 Teams ( Persistent Segment Tree + Stack Monotonicity )

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

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值的總和,條件形式複雜,如果不加功夫用持久化線段樹亂搞…

UVA 12538 Version Controlled IDE ( 持久化隨機二元搜尋樹 )

UVa Online Judge - Offline Here are some good resources I read through in order to understand how to implement persistent RBST for this problem. morris821028.github.io blog.csdn.net #include <bits/stdc++.h> using namespace std; const int MAXMEM = 5e7; co</bits/stdc++.h>…

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…