線段樹

1/17ページ

HUD3954-Level up(線段樹技巧)

題目大意: 有N個英雄,初始為1級,0經驗。有M波怪物,每波怪物選擇區間[l,r]的英雄去打,打死每波怪物的英雄會獲得k(等級)*ei的經驗,現在給出升到每個等級所需要的經驗,和每波怪物派出的英雄,每次詢問一個區間內經驗值最高的值。 思路: 一道線段樹區間更新變形題,容易想到每次更新對每個子區間的改 […]

[洛谷模板大賽]題解 模板整理QAQ

題目地址:NOIP RP 題目描述不用說,都是交模板就能AC的,昨晚就A了4個題因為時間不太夠了…… 最近也想整理模板,看到這麼個模板大賽自然是把持不住辣~ 除了T2平衡樹不會做之外其他的都可以,T5好像是遞迴版Spfa,現學了一下,其實思想都一樣,不用學,其他的沒什麼了,看模板~ T1:線段樹: […]

線段樹 例題

A – 敵兵佈陣  C國的死對頭A國這段時間正在進行軍事演習,所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線佈置了N個工兵營地,Derek和Tidy的任務就是要監視這些工兵營地的活動情況。由於採取了某種先進的監測手段,所以每個工兵營地的人數C國都掌握的一清二楚 […]

Jzoj5234 外星人的路徑

有一個外星人控制了你的大腦。一開始你處於原點(0,0)。外星人有一個由(R,U,D,L)組成的長度為M 的操作序列,分別代表(右,上,下,左)。 平面上有N 個關鍵點,每當外星人給出一個操作,你需要在這個方向上找到最近的一個關鍵點,並走到那個點上。保證輸入資料合法。 100%的資料,N,M≤1000 […]

ST表

ST表學習 作用:ST演算法是用來求解給定區間RMQ的最值,本文以最小值為例 舉例: 給出一陣列A[0~5] = {5,4,6,10,1,12},則區間[2,5]之間的最值為1。 方法:ST演算法分成兩部分:離線預處理 (nlogn)和 線上查詢(O(1))。雖然還可以使用線段樹、樹狀連結串列等求解 […]