2024.2.2 鮮花
aLIEz
決めつけばかり
自惚れを著たチープな hokori で
音荒げても
棚に隠した哀れな
恥に濡れた鏡の中
都合の傷だけひけらかして
手軽な強さで勝取る術を
どれだけ磨いでも気はやつれる
ふらついた思想通りだ
愛-same-CRIER 愛撫-save-LIAR
Eid-聖-Rising HELL
愛してる game 世界の day
Don't-生-War Lie-兵士-War-World
Eyes-Hate-War
A-Z Looser-Krankheit-Was IS das?
受け売り盾に見下してても
そこには地面しかない事さえ
気付かぬままに壊れた
過去に負けた鏡の奧
どこまで叫べば位置を知れる
とどめもないまま息が切れる
堂々さらした罪の群れと
後ろ向きにあらがう
愛-same-CRIER 愛撫-save-LIAR
Aid-聖-Rising HELL
I'll-ness Reset-Endじゃない Burst
Don't-生-War Lie-兵士-War-World
Eyes-Hate-War
A-Z 想像High-de-Siehst YOU das?
偽の態度な臆病loud voice
気高さを勘違いした心臓音
狙い通りの幻見ても
満たせない何度も目を開けても
どこまで叫べば位置を知れる
とどめもないまま息が切れる
堂々さらした罪の群れと
後ろ向きにあらがう
愛-same-CRIER 愛撫-save-LIAR
Eid-聖-Rising HELL
愛してる Game世界のDay
Don't-生-War Lie-兵士-War-World
Eyes-Hate-War
A-Z Looser-Krankheit-Was IS das?
Leben was ist das?
Signal siehst du das?
Rade die du nicht weisst
Aus eigenem willen
Leben was ist das?
Signal siehst du das?
Rade die du nicht weisst
Sieh mit deinen augen

P2305 [NOI2014] 購票
有點牛的題。
在序列上的部分是顯,考慮上樹。
發現加可撤銷直接上,但是可撤銷李超要精細卡空間,有沒有不用卡空間的呢?
-
可撤銷單調棧:
就是你每次插入都二分最終位置而不是依次彈出,這樣復雜度就不基于均攤了,并且每次最多修改 \(O(1)\) 個位置,撤銷直接撤。
然后用樹狀數組套一下即可優秀空間。
-
點分治:
有根樹的點分確實有點牛。
具體的就是對于一顆以 \(R\) 為根的樹,先找到它的重心 \(T\),分治上下部分,在統計上部分對下部分的貢獻即可。
-
樹剖:
樸素樹剖是 \(log^3\) 的。
考慮一個很牛的 trick。我們發現對于每個鏈的劃分都是一些重鏈的前綴和一個重鏈的中段,考慮預處理出所以重鏈的貢獻,就可以做 \(log^2\) 了。
實現時可以考慮直接將查詢掛在重鏈上先掃一遍,也可以在處理到這條鏈時考慮對子樹的貢獻,如果按照第二種寫法,就會寫成廣為人知的鏈分即 dsu on tree(每次先貢獻所有輕兒子,在跑重兒子,最后清空跑輕兒子)。
這里給出可撤銷的代碼:
Code
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using ull = unsigned long long;
using llf = long double;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in_out/in.in", "r", stdin), *OutFile = freopen("in_out/out.out", "w", stdout);
#endif
const int N = 2e5 + 3;
int n, t; llt cq[N], cp[N], cl[N];
class Stk{
private:
vector<pair<llt, llt>> stk; int top = -1;
stack<tuple<pair<llt, llt>, int, int>> clr;
public:
void Epl(llt x, llt y){
auto Chg = [&](int p){
if(stk.size() == p)
stk.emplace_back(0, 0);
clr.emplace(stk[p], p, top);
stk[top = p] = {x, y};
};
auto Chk = [&](int k){
auto &[xa, ya] = stk[k - 1]; auto &[xb, yb] = stk[k];
return (ya - yb) * 1. / (xa - xb) > (yb - y) * 1. / (xb - x);
};
int l = 1, r = top;
while(l <= r){
int mid = l + r >> 1;
if(Chk(mid)) r = mid - 1;
else l = mid + 1;
}
Chg(r + 1);
}
bool Ept(){
return top < 0;
}
pair<llt, llt> &Get(llt s){
auto Chk = [&](int k){
auto &[xa, ya] = stk[k - 1]; auto &[xb, yb] = stk[k];
return (ya - yb) * 1. / (xa - xb) > s;
};
int l = 1, r = top;
while(l <= r){
int mid = l + r >> 1;
if(Chk(mid)) r = mid - 1;
else l = mid + 1;
}
return stk[r];
}
void Re(){
auto &[sk, p, tp] = clr.top(); clr.pop();
stk[p] = sk, top = tp;
}
};
class Bit{
private:
Stk a[N];
int Low(int x){
return x & -x;
}
public:
void Ins(int p, llt x, llt y){
for(int i = p; i; i -= Low(i))
a[i].Epl(x, y);
}
llt Get(int p, llt k){
auto Val = [&](const pair<llt, llt> &t){
auto &[x, y] = t;
return -k * x + y;
};
llt ans = 0x3f3f3f3f3f3f3f3f;
for(int i = p; i <= N; i += Low(i))
if(!a[i].Ept()) ans = min(ans, Val(a[i].Get(k)));
return ans;
}
void Re(int p){
for(int i = p; i; i -= Low(i))
a[i].Re();
}
} bt;
struct Gph{
vector<pair<int, llt>> to[N];
void Add(int u, int v, llt w){
to[u].emplace_back(v, w);
}
void ADD(int u, int v, llt w){
Add(u, v, w), Add(v, u, w);
}
#define For_to(i, u, v, w, g) for(auto &[v, w] : g.to[u])
} g;
llt dp[N], dep[N]; int stk[N], top;
void Dfs(int u, llt ds){
dep[stk[++top] = u] = ds;
int l = 1, r = top - 1;
while(l <= r){
int mid = l + r >> 1;
if(dep[stk[mid]] + cl[u] >= ds) r = mid - 1;
else l = mid + 1;
}
dp[u] = bt.Get(l, cp[u]) + cp[u] * ds + cq[u];
bt.Ins(top, ds, dp[u]);
For_to(i, u, v, w, g)
Dfs(v, ds + w);
bt.Re(top), --top;
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> t;
for(int i = 2; i <= n; ++i){
int f; llt s;
cin >> f >> s >> cp[i] >> cq[i] >> cl[i];
g.Add(f, i, s);
}
bt.Ins(1, 0, 0), stk[top = 1] = 1;
memset(dp, 0x3f3f3f3f, sizeof(dp)), dp[1] = 0;
For_to(i, 1, v, w, g)
Dfs(v, w);
for(int i = 2; i <= n; ++i)
cout << dp[i] << endl;
}
zzz 體驗
想了想還是放好了。
早想玩玩二游,在開學的前四天晚上經過不怎么仔細的考慮選擇了 zzz。
事實上一共就玩了一坤天,感覺不錯。
好像說大改了走格子,反正改了以后的感覺十分不錯。
感覺第五章的劇情太趕了,但考慮 1.4 大改,也還能接受。
打斗很爽,難度還是有的,可能是我懶得養,一個二游被我玩出了魂類游戲的感覺也是沒救了,感謝閃避,感謝彈刀。
三分鐘日常喜了,三分鐘日常也沒人給我做惱了。
就是抽嘉音結果吧貓又的隊都抽出來了確實是地獄了,最后拼盡全力也沒出……
某濤:我有理由合理的懷疑一下你這東西的抽取概率(
本來這里應該有一張 zzz 的圖,因為沒有機會找,所以不放了。
P


本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18690966
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號