2025.3.27 鮮花

如何優雅的使用 stl

啥背景，殺烏雞

Viumbe vyote vya mungu wetu na mfalme wetu
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti
Pazeni sauti
Viumbe vyote vya mungu wetu na mfalme wetu
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Viumbe vyote vya mungu wetu na mfalme wetu
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti
Pazeni sauti
Pazeni sauti ili nasi mwimbe
Pazeni
Pazeni
Pazeni
PazeniPazeni
Pazeni
Viumbe vyote vya mungu wetu na mfalme wetu
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti ili nasi mwimbe
Pazeni sauti
Pazeni sauti
Pazeni sauti ili nasi mwimbePazeni sauti
Pazeni sauti
Pazeni sauti
Pazeni sauti

眾所周知的，priority_queue 可以通過一下方式傳 lambda 比較函數。

auto Cmp = [](int a, int b){return a > b;};
priority_queue<int, vector<int>, decltype(Cmp)> que(Cmp);

有沒有不定義 Cmp 的辦法呢？

我們用

#include <cxxabi.h>
cout << abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, nullptr) << endl;

輸出一下 decltype(Cmp) 到底是什么類型，它其實是一個 lambda 的類型，根本沒法輸出。

我們翻找 priority_queue 的原理，容易發現其調用了一個構造函數

priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
    : c(std::move(__s)), comp(__x)
    { std::make_heap(c.begin(), c.end(), comp); }

所以它內置了一個比較對象，而我們傳入的第三個參就是其類型，我們可以通過構造函數來初始化這個對象。

于是我們用 function 替換掉 decltype 即可：

priority_queue<int, vector<int>, function<bool(int, int)>> que([](int a, int b){return a > b;});

事實上，我們可以自己寫一個類似的東西，形如：

template <class T>
class A{
	T f;
	A() = default;
	A(auto k) : f(k){}
};

注意在 C++20 以前 lambda/function 是不能作為值傳入 template 的。

當然你也可以用昨天鮮花的內容轉成函數指針來傳入。

眾所周知，可以用 #define protected public 訪問 queue 或 stack 的底層結構，類似：

#define protected public
#include <stack>
#include <queue>
#undef protected
 
queue<int> que;
for(int i = 1; i <= 10; ++i)
	que.emplace(i);
for(int i = 9; ~i; --i)
	cout << que.c[i] << ' ';

這個其實可以擴展。

對于 priority_queue，我們類似做

#define protected public
#include <stack>
#include <queue>
#undef protected
 
priority_queue<int> que;
for(int i = 1; i <= 10; ++i)
	que.emplace(i);
for(int i = 9; ~i; --i)
	cout << que.c[i] << ' ';

發現并不是有序的。

這是因為其內部是通過 make_heap 實現的，詳細了解可以直接搜，這里說一下如何讓他有序。

用 sort_heap(que.c.begin(), que.c.end(), less<int>())，less<int>() 是 que 的比較函數，注意這里是倒序的。

想還原可以用 make_heap(que.c.begin(), que.c.end(), less<int>())

對于 bitset，我們也可以直接訪問，形如：

#define private public
#include <bitset>
#undef private

bitset<10000> s;
s._M_w[i];

默認是用 long 壓的，一般是 \(64\)，注意就是這個是 private，并且是 ._M_w[]。

這樣其實就解決了必須手寫 bitset 的一個方面。

給出 P11831 [省選聯考 2025] 追憶的代碼。~~甚至比我手寫快~~

Code

/* Local File
in_out/in.in
in_out/out.out
*/
#define private public
#include <bitset>
#undef private
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using ull = unsigned long long;
using llf = long double;
#define endl '\n'
 
const int N = 1e5 + 3, W = 64, D = N / W + 1, B = 600, S = N / B + 3;
int n, m, q, va[N], vb[N], pa[N], pb[N];

bitset<N> sn[N], ca[S], cb[S];
int bln, id[N], bl[N], br[N];

struct Gph{
	vector<int> to[N];
	void Add(int u, int v){
		to[u].emplace_back(v);
	}
	void ADD(int u, int v){
		Add(u, v), Add(v, u);
	}
	void Clr(){
		for(int i = 1; i <= n; ++i)
			to[i].clear();
	}
#define For_to(u, v, g) for(auto v : g.to[u])
} g, rg;

int rd[N];
void Solve(){
	cin >> n >> m >> q;
	for(int i = 1; i <= m; ++i){
		int u, v; cin >> u >> v;
		g.Add(u, v), ++rd[u], rg.Add(v, u);
	}
	for(int i = 1; i <= n; ++i)
		cin >> va[i], pa[va[i]] = i;
	for(int i = 1; i <= n; ++i)
		cin >> vb[i], pb[vb[i]] = i;
	queue<int> que;
	for(int i = 1; i <= n; ++i) if(!rd[i])
		que.emplace(i);
	while(!que.empty()){
		int u = que.front(); que.pop();
		sn[u][u] = 1;
		For_to(u, v, g) sn[u] |= sn[v];
		For_to(u, v, rg)
			if(!--rd[v]) que.emplace(v);
	}
	bln = 0;
	for(int l = 1; l <= n; l += B){
		++bln;
		for(int j = bl[bln] = l, r = br[bln] = min(l + B - 1, n); j <= r; ++j)
			ca[bln][pa[j]] = 1, cb[bln][pb[j]] = 1, id[j] = bln;
	}
	for(int i = bln - 1; i; --i)
		ca[i] |= ca[i + 1], cb[i] |= cb[i + 1];
	for(int tst = 1; tst <= q; ++tst){
		int op; cin >> op;
		if(op == 1){
			int x, y; cin >> x >> y;
			int ix = id[va[x]], iy = id[va[y]];
			swap(va[x], va[y]), pa[va[x]] = x, pa[va[y]] = y;
			for(int i = 1; i <= ix; ++i) ca[i][x] = 0;
			for(int i = 1; i <= iy; ++i) ca[i][x] = 1;
			for(int i = 1; i <= iy; ++i) ca[i][y] = 0;
			for(int i = 1; i <= ix; ++i) ca[i][y] = 1;
		}else if(op == 2){
			int x, y; cin >> x >> y;
			int ix = id[vb[x]], iy = id[vb[y]];
			swap(vb[x], vb[y]), pb[vb[x]] = x, pb[vb[y]] = y;
			for(int i = 1; i <= ix; ++i) cb[i][x] = 0;
			for(int i = 1; i <= iy; ++i) cb[i][x] = 1;
			for(int i = 1; i <= iy; ++i) cb[i][y] = 0;
			for(int i = 1; i <= ix; ++i) cb[i][y] = 1;
		}else{
			int u, l, r; cin >> u >> l >> r;
			int il = id[l], ir = id[r];
			bitset<N> k(ca[il] ^ ca[ir]);
			for(int i = bl[ir]; i <= r; ++i) k[pa[i]] = 1;
			for(int i = bl[il]; i < l; ++i) k[pa[i]] = 0;
			k &= sn[u];
			int p = 0;
			for(int i = 0; i < D; ++i)
				while(p < bln && (cb[p + 1]._M_w[i] & k._M_w[i])) ++p;
			if(!p) cout << 0 << endl;
			else
				for(int i = br[p]; i >= bl[p]; --i){
					int p = pb[i];
					if(k[p]){
						cout << i << endl;
						break;
					}
				}
		}
	}
}

void Clear(){
	memset(sn, 0, sizeof sn);
	memset(ca, 0, sizeof ca);
	memset(cb, 0, sizeof cb);
	g.Clr(), rg.Clr();
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int c, t; cin >> c >> t;
	while(t--) Solve(), Clear();
}

眾所周知，在 tr2/dynamic_bitset 頭文件中有一個 dynamic_bitset，其支持動態 resize。

具體可以看 dynamic_bitset。

但是眾所不周知，其 is_subset_of （話說這個 subset 竟然是后綴）寫掛了……

所以你直接用 is_subset_of 會 CE。

5k 曾給出過:

#define is_proper_subset_of is_subset_of(const dynamic_bitset& __b)\
	{ return this->_M_is_subset_of(__b); }\
	bool qwq

我們分析一下原因。

翻找源碼：

bool _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept{
	if (__b._M_w.size() == this->_M_w.size()){
	    for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
			if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
				return false;
	    return true;
	}else return false;
}

bool is_subset_of(const dynamic_bitset& __b) const
	{ return this->_M_is_subset_of(__b); }

容易發現其問題：在 bool _M_is_subset_of(const __dynamic_bitset_base& __b) 后少了一個 const。

寫源代碼不編譯的人這輩子有了。

但是我們不太能直接加上一個 const，于是我們曲線救國，把 is_proper_subset_of define 成一個新的 is_subset_of 即可。

這樣就不能用 is_proper_subset_of 了（當然也不能用 qwq 做變量名），但事實上是 is_proper_subset_of 的源碼更絕望，其有好多錯特別不好改，還是用 is_subset_of && != 替代吧。

其實要是只是想用的話有更簡單的方式，我們發現 is_subset_of 本質上就是調用了一個 _M_is_subset_of，并且 dynamic_bitset 和 __dynamic_bitset_base 之間可直接轉換，所以如下即可：

#define private public
#include <tr2/dynamic_bitset>
#undef private

tr2::dynamic_bitset<> a, b;
a._M_is_subset_of(b);

posted @ 2025-03-27 07:49 xrlong 閱讀(58) 評論(2) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

2025.3.27 鮮花

如何優雅的使用 stl

公告

Loading