不詳細揭秘在線決策單調性 DP 的單 log 分治做法——2025.8.23 鮮花

不詳細揭秘在線決策單調性 DP 的單 log 分治做法

不詳細揭秘在線決策單調性 DP 的單 \(\log\) 分治做法

Cherry Pop

わーどきどき　ねーすきすき？
哇～心跳加速 吶～喜歡喜歡？
あーズキズキ　ちねちねちねちね
啊～刺痛刺痛 去死去死去死去死
あたし一等賞がほしいのよ
人家是要拿第一名的
二番なんて望んでない
才不稀罕當第二呢
みんなめんどくせって離れるの
大家都嫌麻煩 全都躲開我
重い子って不人気なん　なんなん
“重女”就是沒人氣 搞什么嘛
あたし迷子　迷子で損な感じ
我總是迷路 感覺迷路怪吃虧的
本命になれないマン　死んじまうわ！
當不成你的本命 我要死掉啦！
サイコ？　サイコはどっちどっち
地雷女？誰才是 誰才是地雷女？
おまえのことは顔しか　信じらんない！
你這個人 除了臉還有哪里可信！
やってないね　やってらんないね
弄不下去了 真是受不了
一生ぼっち　好意ありがとさん
你就注孤生吧 好意心領啦
やってられるか～ったかたったった！
這誰受得了啊～啦 噠噠噠噠噠！
まじで
咱說實話
愛していい感　すきすき？
可以愛的感覺 喜歡喜歡？
戀していい感　すきすき？
可以喜歡的感覺 喜歡喜歡？
どれみが怖いぞ　チェリーチェリー
Do Re Mi 好可怕喲 Cherry Cherry
そうでもない感　むりむり？
感覺 “也就那樣吧”不行不行？
どうでもいい感　むりむり？
感覺 “無所謂啦” 不行不行？
トゲみが怖いぞ　ベイビーベイビー
帶刺兒的感覺好可怕哦 Baby Baby
愛していい感　すきすき？
可以愛的感覺 喜歡喜歡？
戀していい感　すきすき？
可以喜歡的感覺 喜歡喜歡？
都合が良くてよ　チェリーチェリー
倒是挺會占便宜嘛 Cherry Cherry
そうでもない感　むりむり？
感覺 “也就那樣吧”不行不行？
どうでもいい感　むりむり？
感覺 “無所謂啦” 不行不行？
出直してきなよ　ベイビーベイビー
給我重新來過啦 Baby Baby
いやーほんと…
哎呀—真是的…
わーどきどき　ねーすきすき？
哇～心跳加速 吶～喜歡喜歡？
あーズキズキ　ちねちねちねちね
啊～刺痛刺痛 去死去死去死去死
あたし一等賞がほしいのよ
本公主要拿第一名喲
二番なんて望んでない
才不稀罕當第二呢
時に先生　好きとはなんですか
有時也會問問老師 “喜歡”到底是什么呀
辭書にないやつをください
給我一個字典里沒有的答案吧
怒りぐっとこらえて言う「ごめんね」
強壓怒火 說聲「抱歉啦」
おまえのすきはすきじゃない　吐いちまうわ！
你的喜歡算什么喜歡 要吐了啦！
終わったおバカはどっかいって
沒救了的笨蛋 快快消失吧！
あたしは王子様を待っているの
人家可是在等王子殿下的
やってないね　やってらんないね
弄不下去了 真是受不了
殺菌よろしく　ピュアに敬禮
快給我消毒 向純潔致敬！
やってないね　やってらんないね
我才沒干過 真是受不了
一生ぼっち　好意ありがとさん
你就注孤生吧 好意心領啦
やってられるか～！
我真的受不了了~！
まじで…はぁ…ったかたったった！
真的啦…哈啊…咔噠噠噠噠！
まじで
真的啦
愛していい感　すきすき？
可以愛的感覺 喜歡喜歡？
戀していい感　すきすき？
可以喜歡的感覺 喜歡喜歡？
どれみが怖いぞ　チェリーチェリー
Do Re Mi 好可怕喲 Cherry Cherry
そうでもない感　むりむり？
感覺 “也就那樣吧”不行不行？
どうでもいい感　むりむり？
感覺 “無所謂啦” 不行不行？
トゲみが怖いぞ　ベイビーベイビー
帶刺兒的感覺好可怕哦 Baby Baby
愛していい感　すきすき？
可以愛的感覺 喜歡喜歡？
戀していい感　すきすき？
可以喜歡的感覺 喜歡喜歡？
都合が良くてよ　チェリーチェリー
倒是正合心意 Cherry Cherry
そうでもない感　むりむり？
感覺 “也就那樣吧”不行不行？
どうでもいい感　むりむり？
感覺 “無所謂啦” 不行不行？
出直してきなよ　ベイビーベイビー
給我重新來過啦 Baby Baby
はい解散
好 解散！
わーどきどき　ねーすきすき？
哇～心跳加速 吶～喜歡喜歡？
あーズキズキ　ちねちねちねちね
啊～刺痛刺痛 去死吧去死吧去死吧去死吧
せーのっ
預備——起！

2c9c215044fdafa1d4cbb259cda10bb44040314d

有說法叫簡易版 LARSCH 算法。

有抄襲參考 Register_int 的在線決策單調性地皮還能單老哥分治做？ - 洛谷專欄。

感覺有點將 Cdq 和離線分治混起來寫的感覺。

有點牛。

考慮一個函數 \(S(l, r)\)，我們希望調用這個函數獲得 \(dp_l \sim dp_r\) 的值。

顯然不分段算貢獻是不現實的，所以我們分段算。

我們認為調用 \(S(l, r)\) 時 \(dp_1\sim dp_{l - 1}\) 都是處理好的，\(i \in [1, l)\) 對 \(dp_r\) 的貢獻時已經處理好的，設 \(i\) 的決策點時 \(p_i\)（注意此時不區分是否完全轉移好）。

我們：

枚舉 \(j \in [p_{l - 1}, p_r]\) 更新 \(dp_{mid}\)。
遞歸 \(S(l, mid)\)。
用 \(j\in [l, mid]\) 更新 \(dp_{r}\)。
遞歸 \(S(mid + 1, r)\)。

復雜度和正確性都比較顯然。

十分甚至九分的好寫，更牛的是可以用離線分治的莫隊，唯一要注意的是第一步和第三步的莫隊分開開。

例題：
ABC355G G - Baseball

Code

/*
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && time ./%< && size %<
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && time ./%< && size %<
echo && cat out.out && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endif
 
const int N = 1e5 + 3;
llt dp[N], sp[N], si[N], _a; int n, _k, ps[N];

llt Wt(int l, int r){
	if(!l) return r * sp[r] - si[r];
	else if(r > n) return si[n] - si[l - 1] - l * (sp[n] - sp[l - 1]);
	int mid = (l + r) >> 1;
	return si[mid] - si[l - 1] - l * (sp[mid] - sp[l - 1]) + r * (sp[r] - sp[mid]) - si[r] + si[mid];
}
void Upd(int i, int j){ llt v = dp[i] + Wt(i, j) - _a; if(dp[j] > v) dp[j] = v, ps[j] = i; }
void Dp(int l, int r){
	if(l == r) return ;
	int mid = (l + r) >> 1;
	for(int i = ps[l - 1]; i <= ps[r] && i < mid; ++i) Upd(i, mid);
	Dp(l, mid);
	for(int i = l; i <= mid; ++i) Upd(i, r);
	Dp(mid + 1, r);
}
llt F(){
	memset(dp + 1, 0x3f, sizeof(*dp) * n), Upd(0, n), Dp(1, n);
	llt mi = 0x3f3f3f3f3f3f3f3f;
	for(int i = 1; i <= n; ++i) mi = min(mi, dp[i] + Wt(i, n + 1));
	return mi;
}
llt Wqs(){
	auto G = [](llt a){ return _a = a, F() + a * _k; };
	llt l = -1e12, r = 1e12;
	while(l <= r){
		llt mid = (l + r) >> 1, a = G(mid), b = G(mid + 1);
		if(a == b) return a;
		else if(a < b) l = mid + 1;
		else r = mid - 1;
	}
	return G(l);
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> _k;
	for(int i = 1; i <= n; ++i) cin >> sp[i], si[i] = sp[i] * i + si[i - 1], sp[i] += sp[i - 1];
	cout << Wqs() << endl;
}

CF868F Yet Another Minimization Problem

這個是離線莫隊維護貢獻的板子，懶得寫了。

P9266 【PA 2022】 Nawiasowe podzia?y

Code

/*
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra && time ./%< && size %<
ulimit -s 128000 && clear && g++ % -o %< -O2 -std=c++14 -DLOCAL -Wall -Wextra -fsanitize=address,undefined -g && time ./%< && size %<
echo && cat out.out && echo
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using llf = long double;
using ull = unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile = freopen("in.in", "r", stdin), *OutFile = freopen("out.out", "w", stdout);
#endif

const int N = 1e5 + 3;
int n, _k, _a[N], pl[N], pr[N], sl[N], sr[N];

class MO{
private:
	int l = 1, r = 0; llt ans = 0;
	int __tu[N << 1], *const tu = __tu + N;
public:
	llt Qry(int ql, int qr){
		++qr;
		while(r < qr){
			++r;
			if(pl[r] < l) ans += tu[_a[r]];
			else ans += sl[r];
			++tu[_a[r]];
		}
		while(l > ql){
			--l;
			if(pr[l] > r) ans += tu[_a[l]];
			else ans += sr[l];
			++tu[_a[l]];
		}
		while(r > qr){
			--tu[_a[r]];
			if(pl[r] < l) ans -= tu[_a[r]];
			else ans -= sl[r];
			--r;
		}
		while(l < ql){
			--tu[_a[l]];
			if(pr[l] > r) ans -= tu[_a[l]];
			else ans -= sr[l];
			++l;
		}
		return ans;
	}
} M1, M2;

namespace WQS{
	int ps[N]; llt dp[N], _a = 0;
	void Upd(int j, int i, auto &M){
		llt v = dp[j] + M.Qry(j + 1, i) - _a;
		if(dp[i] > v) dp[i] = v, ps[i] = j;
	}
	void Dp(int l, int r){
		if(l == r) return ;
		int mid = (l + r) >> 1;
		for(int i = ps[l - 1]; i <= ps[r] && i < mid; ++i) Upd(i, mid, M1);
		Dp(l, mid);
		for(int i = l; i <= mid; ++i) Upd(i, r, M2);
		Dp(mid + 1, r);
	}
	llt F(){
		memset(dp + 1, 0x3f, sizeof(*dp) * n), Upd(0, n, M1);
		return Dp(1, n), dp[n];
	}
	llt Wqs(){
		auto G = [](llt a){ return _a = a, F() + a * _k; };
		llt l = -1e10, r = 1e10;
		while(l <= r){
			llt mid = (l + r) >> 1, a = G(mid), b = G(mid + 1);
			if(a == b) return a;
			else if(a < b) l = mid + 1;
			else r = mid - 1;
		}
		return G(l);
	}
}

vector<pair<int, int>> qry[N];
int __tu[N << 1], *const tu = __tu + N;
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> _k; ++n;
	for(int i = 2; i <= n; ++i){ char c; cin >> c, _a[i] = (c == '(' ? 1 : -1) + _a[i - 1]; }
	stack<int> stk; _a[0] = -0x3f3f3f3f, _a[n + 1] = -0x3f3f3f3f, stk.emplace(0);
	for(int i = 1; i <= n + 1; ++i){
		while(_a[stk.top()] > _a[i]) pr[stk.top()] = i, stk.pop();
		stk.emplace(i);
	}
	stk.pop(), stk.pop(), stk.emplace(n + 1);
	for(int i = n; ~i; --i){
		while(_a[stk.top()] > _a[i]) pl[stk.top()] = i, stk.pop();
		stk.emplace(i);
	}
	for(int i = 1; i <= n; ++i) qry[max(1, pl[i]) - 1].emplace_back(i, -1), qry[i - 1].emplace_back(i, 1);
	for(int i = 1; i <= n; ++i){
		++tu[_a[i]];
		for(auto [k, v] : qry[i]) sl[k] += tu[_a[k]] * v;
		qry[i].clear();
	}
	memset(__tu, 0, sizeof __tu);
	for(int i = 1; i <= n; ++i) qry[i].emplace_back(i, -1), qry[min(pr[i], n)].emplace_back(i, 1);
	for(int i = 1; i <= n; ++i){
		++tu[_a[i]];
		for(auto [k, v] : qry[i]) sr[k] += tu[_a[k]] * v;
		qry[i].clear();
	}
	--n;
	cout << WQS::Wqs();
}

posted @ 2025-08-23 17:49 xrlong 閱讀(64) 評論(2) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

不詳細揭秘在線決策單調性 DP 的單 log 分治做法——2025.8.23 鮮花

不詳細揭秘在線決策單調性 DP 的單 \(\log\) 分治做法

公告

Loading