251025B. 海嘯

有 \(n\) 個物品，物品 \(i\) 有 \(v_i\) 的價值和 \(2^{w_i}\) 的體積。

以及 \(q\) 次修改，每次給出 \(x\) 并令 \(a_x \leftarrow a_x +1\)。

每次修改后求出當總體積 \(\le V\) 時的最大總價值。

\[n\le 2\times 10^5,q\le 10^4, V\le 10^{18} \]

先考慮沒有修改怎么做

稱 \(w_i\) 相同的所有物品都在第 \(w_i\) 層。

我們先把每一層內部排序，然后考慮從小往大貪心。

對于第 \(w\) 層，假如 \(V\) 二進制下第 \(w\) 位為 \(1\)，那么取出最大的價值 \(v_0\)，將 \(v_0\) 累加到答案里，然后將其刪去。

對于剩下的數，我們從大到小將每兩個相鄰的物品捆綁加入下一層。

這個過程可以歸并解決。

考慮怎么帶上修改？

我們從 \(w_x\) 開始依次枚舉層，并考慮他造成的影響。

考慮到我們僅關心價值，不關心具體是哪個物品貢獻的，我們在當前層二分找到第一個 \(\le v_x\) 的，然后將他 \(+1\)。

然后我們模仿剛才的過程，將這個物品和相鄰的捆綁，并在下一層二分找到對應的物品，將權值 \(+1\)。

一直重復這個過程直到某一層 \(w\) 上這個價值是該層最大值，并且 \(V\) 二進制下第 \(w\) 位為 \(1\)。那么直接將答案 \(+1\)，然后退出這個過程。

時間復雜度 \(\mathcal O(n\log V+q\log n\log V)\)。

code

#include <iostream>
#include <algorithm>
#include <cstring>

const int N = 3e5 + 7, W = 60;
typedef long long i64;
#define rep(i,a,b) for(int i(a);i<=(b);++i)

namespace suki {

i64 sp, ans;
int n, q, w[N], v[N];
std::basic_string<i64> g[W]; 
auto cmp = std::greater<i64>();

inline void reset() { ans = 0; for(int i = 0; i < W; ++i) g[i].clear(); }

inline void main() {
	std::cin >> n >> sp >> q;
	rep(i, 1, n) std::cin >> w[i] >> v[i], g[w[i]] += v[i];
	for(int i = 0; i < W; ++i) std::sort(g[i].begin(), g[i].end(), cmp);

	auto work = [&](int k) {
		if(k > 0) {
			int origs = g[k].size(), shift = sp >> (k - 1) & 1;
			for(int i = shift; i + 1 < (int)g[k-1].size(); i += 2)
				g[k] += g[k-1][i+1] + g[k-1][i];
			if((g[k-1].size() - shift) & 1) g[k] += g[k-1].back();
			std::inplace_merge(g[k].begin(), g[k].begin() + origs, g[k].end(), cmp);
		}
		if((sp >> k & 1) && !g[k].empty()) { ans += g[k][0]; }
	};
	for(int i = 0; i < W; ++i) work(i);
	std::cout << ans << "\n";

	for(; q--; ) {
		int x; std::cin >> x;

		auto modify = [](int id) {
			i64 val = v[id]++;
			for(int k = w[id]; k < W; ++k) {
				int p = std::lower_bound(g[k].begin(), g[k].end(), val, cmp) - g[k].begin();
				int shift = sp >> k & 1; g[k][p]++;
				if(shift && (p == 0)) { ++ans; return ; }
				int q = ((p - shift) ^ 1) + shift;
				if(0 <= q && q < g[k].size()) val += g[k][q];
			}
		};
		modify(x);
		std::cout << ans << "\n";
	}
}

};

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	int t; std::cin >> t;
	for(; t--; ) { suki::reset(), suki::main(); }
}

之前見過一道相似的題，但是找不到原題了。題意如下：

給定一個大小為 \(n\) 的可重集 \(S={a_i}\)。

維護以下兩種操作：

將第 \(l\) 大到第 \(r\) 大之間的所有數 \(+1\)。
詢問第 \(l\) 大到第 \(r\) 大之間的所有數的和。

\[n\le 10^6 \]

我們初始先將 \(a\) 排序，然后直接按順序放到線段樹上，所以初始時整個序列是有序的。

對于一次修改操作 \([l,r]\)，令 \(x=a_l,y=a_r\)，\(p_0\) 是 \(y\) 第一次出現的位置，\(p_1\) 是 \(y\) 最后一次出現的位置。

假如我們將整個序列拆成三部分：\([1,p_0-1],[p_0,p_1],[p_1+1,n]\)。

對于第一部分，我們修改的是一個后綴，所以直接在原位置上加不會破壞有序的性質。

對于中間的部分，由于值全部相同，我們可以將位于前綴的修改平移到后綴上，這個時候仍然不會破壞有序的性質。

對于最后一部分，我們沒有修改，所以不會破壞有序的性質。

第一部分的最后一個數修改后 \(\le y\)，中間部分的第一個數修改后 \(\ge y\)，所以我們將前兩段拼起來整體仍然滿足有序的性質。

中間部分的最后一個數修改后 \(\le y+1\)，最后一部分的第一個數 \(\ge y+1\)，所以我們將后兩段拼起來整體仍然滿足有序的性質。

換句話說我們可以將每個修改拆成最多兩個區間，使得直接在原位置上修改后整個序列仍然有序。

例如一開始的序列是 01112223334，我們希望做操作 \([4,8]\)。（011[12223]334

那么我們實際上做的區間加是：011[1222]33[3]4。加完后的結果是：01123333344。

總而言之，這兩個問題的維護方法，本質上都是利用了 \(+1\) 操作不會造成“交換”的性質，這使得我們直接在原位上對序列進行操作成為可能。

posted @ 2025-10-26 00:13 CuteNess 閱讀(16) 評論(0) 收藏舉報

刷新頁面返回頂部

CuteNess

251025B. 海嘯

251025B. 海嘯

公告