嚴格 wqs 二分——2025.6.5 鮮花

妄想感傷代償連盟

言っちゃった
	
我說了
もう一時だけ隣りに居たい
	
只想暫時待在你的身邊
いやいやまさか 延長は郁雑い
	
不對不對 難道說 繼續下去只會令人厭煩
御免なさい 帰ってね
	
非常抱歉 還是回去吧
二酸化の炭素 きみの濃度
	
二氧化碳 是你的濃度
浸ってたいよ 泥沼の夢に
	
沉浸在泥沼般的夢里
身勝手だって言われてもペロリ
	
就算被說任性也只是吐吐舌頭
不安じゃない 未來はない
	
沒有不安 沒有未來
その顏に生まれ変わりたいな
	
真想脫胎換骨成此面目啊
知っちゃった
	
早知道了
大嫌いを裏返したとて
	
就算把討厭翻個面過來
そこに大好きは隠れてないと
	
那里也不會藏著喜歡
葉えたい この想い
	
想要實現這種愿望
甘え過ぎ太る心回り
	
過度甜蜜增加心情波動
“ファット想い→スリム”を掲げよう
	
主張削減日益膨脹的思念
出逢った頃と同じ様に成ろう
	
變回與相遇時同種的模樣
思い笑描く理想狂
	
笑著描繪回憶的理想狂
血走る愿いはやがて安堵
	
激越之愿也終歸平息
だけど「大丈夫」
	
可是令人完全安心的
なんて戀はどこにもないの
	
戀情已經毫無影蹤了
だから妄想感傷代償連盟
	
所以妄想感傷代價聯盟
愛を懐いて理想を號んだ
	
心執愛情高呼理想
行き場のない愚者のメロディー
	
無處可去愚者旋律
再挑戦?転生?テレポーテーション
	
再挑戰 轉生 瞬間移動
何回だって 重ねて逝くんだ
	
即便多少次 都會再度逝去
終わりなき愛の隨に さあ
	
跟隨著沒有終點的愛 來吧
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭
頑張った
	
努力過了
どうしようもないその我盡
	
無可救藥的那份任性
葉えた先にある謎自戀魔
	
如愿以償后成了自戀狂魔
怒ってる？怒ってない
	
你生氣了 我沒生氣
阿吽の呼吸でズレるビート
	
心有靈犀一般 呼吸偏離了節奏
これがもし映畫やドラマなら
	
如果這是電影或者連續劇的話
スタッフロールまでは乗り切れど
	
我就要直接跳到演職員表了
二度とは観たくない
	
再也不想看第二次
酷すぎる起承 転も結も
	
太殘酷了這起承和轉結
だけど「大丈夫」
	
可我還是相信著
なんて戀を信じて仕舞うよ
	
能令人放心的戀情
通稱：愛情対象年齢
	
通稱 愛情 對象 年齡
愛を悪んで守った位相が
	
憎惡愛情守護地位
正しく歪み始めるの
	
這正是扭曲的開始
最低じゃん
	
最差勁了不是嗎
どうせ対人ローション
	
反正是自我偽裝見機行事
何回だって 傷付け合うんだ
	
即便多少次給予彼此傷害
混ざり合う愛のフィロソフィー
	
也是混雜在愛中的哲理
だけど「大丈夫」なんて噓を覚えて仕舞うの
	
可是我發現了“不用擔心”什么的都是謊言啊
だから
	
所以啊
だから妄想感傷代償連盟
	
所以妄想感傷代價聯盟
愛を懐いて理想を號んだ
	
心執愛情高呼理想
行き場のない愚者のメロディー
	
無處可去愚者旋律
再挑戦?転生?テレポーテーション
	
再挑戰 轉生 瞬間移動
何回だって 重ねて逝くんだ
	
即便多少次 都會再度逝去
終わりなき愛の隨に さあ
	
跟隨著沒有終點的愛 來吧
通稱：愛情対象年齢
	
通稱 愛情 對象 年齡
愛を悪んで守った位相が
	
憎惡愛情守護地位
正しく歪み始めるの
	
這正是扭曲的開始
最低じゃん
	
最差勁了不是嗎
どうせ対人ローション
	
反正是自我偽裝見機行事
何回だって 傷付け合うんだ
	
即便多少次給予彼此傷害
混ざり合う愛のフィロソフィー
	
也是混雜在愛中的哲理
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 なななな
	
愛還是厭 愛還是厭
愛や厭 愛や厭 ななななな
	
愛還是厭 愛還是厭

先簡單說一下傳統的 wqs 二分，不感興趣可以直接跳過，對后面沒影響。

考慮一個上凸的函數 \(f(x)\)，我們希望求得其在 \(k\) 處的取值 \(f(k)\)。

考慮每次用一條直線 \(y = kx + b\) 去切這個凸殼，設交點是 \((x, f(x))\)，則有 \(f(x) = kx + b \Rightarrow b = f(x) - kx\)，若能求 \(f(x) - kx\) 的最大值，則能推出 \(b\)，進而求出交點，并一次調整斜率，使其正好切到 \(k\)。整個過程用二分實現。

但是這個做法會有很多的細節，并不好寫，并且不能高維化。

于是我們學習一下嚴格 wqs 二分。

設 \(g(x) = \max\limits_{a} \{f(a) + ax\} - kx\)，其中 \(k\) 是我們要求的 \(f(k)\) 中的 \(k\)，則 \(g(x)\) 是下凸的（注意和 \(f\) 是相反的）且最小值取到 \(f(k)\)。

嚴格證明可以看 jijidawang 的拉格朗日對偶的相關理論，這里簡單說一下。

考慮求 \(x = k\) 即 \(x - k = 0\) 時 \(\max f(x)\)，有：

\[\begin{aligned}\max f(x) &= \max \{f(x) + \min_\lambda \{\lambda (x - k)\}\} \\ &= \max \min_\lambda \{f(x) + \lambda x - \lambda k\} \\ &= \min_\lambda \max \{f(x) + \lambda x - \lambda k\} \\ &= \min_\lambda \{\max \{f(x) + \lambda x\} - \lambda k\} \\ \end{aligned}\]

其中第三步用了 Minimax 定理，具體內容可以自行搜索。~~我不太會證~~

于是問題變成求單峰函數極值，這個二分和上面的斜率其實是對應的，也就是說可以用整數二分的技巧。

容易將其推廣到高維。

給出一個高維板子 CF1799F Halve or Subtract

Code

/*
clear && g++ % -o %< -O2 -std=c++14 -Wall -Wextra -DLOCAL && time ./%< && size %<
clear && g++ % -o %< -O2 -std=c++14 -fsanitize=address,undefined -g -Wall -Wextra -DLOCAL && time ./%< && size %<
echo && cat in_out/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_out/in.in", "r", stdin), *OutFile = freopen("in_out/out.out", "w", stdout);
#endif

const int N = 5003;
int n, _b, _k1, _k2, _a[N];

llt Clc(int x, int y){
	llt r = 0;
	for(int i = 1; i <= n; ++i)
		r += min({_a[i], ((_a[i] + 1) >> 1) + x, max(_a[i] - _b, 0) + y, max(((_a[i] + 1) >> 1) - _b, 0) + x + y});
	return r;
}
llt Wqs(auto &&f, int k){
	auto g = [&](int x){ return f(x) - 1ll * k * x; };
	int l = -1e9, r = 1e9;
	while(l <= r){
		int mid = (l + r) >> 1; llt 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(0), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while(t--){
		cin >> n >> _b >> _k1 >> _k2;
		for(int i = 1; i <= n; ++i) cin >> _a[i];
		cout << Wqs([&](int x){return Wqs([&](int y){ return Clc(y, x); }, _k1); }, _k2) << endl;
	}
}

posted @ 2025-06-05 22:08 xrlong 閱讀(51) 評論(1) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

嚴格 wqs 二分——2025.6.5 鮮花

嚴格 wqs 二分——2025.6.5 鮮花

公告

Loading