0w1

Fenwick Tree

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

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

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

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

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…

CFR 486 E. LIS of Sequence ( DP, Fenwick Tree )

Problem - E - Codeforces題意: 給一個數列,對每一個值輸出: 1 if 它不屬於任何一個 LIS 2 if 它屬於某個 LIS,但沒有它也存在相同長度的 LIS 3 if 拔掉它的話 LIS 長度會改變制約: N ≤ 1e5 A ≤ 1e5解法: 用 dp 跟 BIT 的要領求出 st_len[ i ]: 以位置 …

POI 18 Stage 3 Meteors ( Parallel Binary Search, Fenwick Tree )

http://main.edu.pl/en/archive/oi/18/met題意: 有 M 個環狀的地,每個地屬於一個人。有 K 次隕石事件,每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人,每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個…

POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod題意: 給一個序列 B,問是否有一個 [ 1, | B | ] 的排列 A,使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。資料規模: In the first line of the standard input there is a positive integer …

CFR 785 E. Anton and Permutation ( RBST on BIT )

Problem - E - Codeforces題意: 一開始你有一個序列 P = { 1, 2, 3, .. N }。處理 Q 筆永久詢問,給 L, R,將 P[ L ] 和 P[ R ] 交換後,輸出當前 P 的逆序述對數。資料規模: The first line of the input contains two integers n and q (1 ≤ n ≤ 200 000…

CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces題意: 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出,對這些子序列分別求,不比該子序列的字典序大的所有子序列的方案數,的總和,對 1e9 + 7 取模。資料規模: The first line contains…

Bangladesh OI 2016 National Round pA. Guess the Queue ( BIT + Deque )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意: 實現一個雙向佇列,可以回答以下三種詢問: 1. ‘1 x y’ ID 為 y 的人從前…

CFR 179 1A. Greg and Array ( BIT )

Problem - A - Codeforces 二回べつべつに区間操作するのは自明。まずどの操作が何回使われるかを統計して終えてから操作毎に区間addをすればいい。 Range add と Single query しかないので BITの方がかなり楽。 追記:いや、普通にarrayの上でいもすすれば…

JOI 10 本選 Planetary Exploration ( 二次元BIT )

Planetary Exploration | Aizu Online Judge なにも考えずに一番先に頭から出たのが二次元BIT。普通にprefix sumでもいけるけど、BITは応用が効くからこれで。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; const int MAXM = 1000 + 3; const</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…

CFR 635 D. Factory Repairs ( BIT )

Problem - D - Codeforces Notice that if the maintenance is made on day p, the maximum sum it could take is prefix sum of min( b, val[ i ] ) + suffix sum of min( a, val[ j ] ) Ɐ i and since the queries are forced to be solved online, we wil…