[OI题解] P11831 [省选联考 2025] 追忆

我该在哪里停留？我问我自己。

一个思路自然、优雅、简单的做法。

题意

将题意用通俗语言表达即需要解决这个问题：DAG 中每个点有特征和权值，均构成排列，支持这些操作：

交换两个点的特征
交换两个点的权值
查询一个点可达的点中，特征在某区间中的点的最大权值。

Keywords & Evaluation

::::info[Keywords] 可达性统计、压位、bitset、拆点、时间轴 ::::

$Difficulty : AT 2700 | (6)$

$Quality : B+$

给思维剪枝

DAG 可达性相关问题一般很强、很具有一般性，注意到本题比 $O (q)$ 次查询 DAG 上两点可达性强：即查询点 $x$ 能否到达编号在 $[y, y]$ 之间的点，就是可达性查询。因此我们考虑 $O (\frac{n q}{w})$ 的做法。（本文默认读者会 bitset 压位解决可达性问题）

积累一些常见的问题的 OI 最优复杂度，提前找到可以规约的复杂度，可以少走很多弯路，如避免在本题中思考 $O ((n + q) polylog (n))$ 做法。

从特殊性质说起我们的思维过程

首先我们尽可能希望不管这个没有任何性质的图，于是我们预处理出每个点可达的点集并压位保存（你先别急具体实现与内存），问题就变为了查询某个点集中，编号在某个区间的点的权值的最大值。

这种多限制的问题，往往我们采用将对象压位，通过限制求交集，来找到满足限制的对象构成的集合（类似 bitset 解决高维偏序），如本题中可以使用将“可达点集”和“ $[l, r]$ 编号点集”求交得到满足条件的点。

在本题中，如果要求权值最大的话，可以根据权值重新编号后使用 _Find_first 找到最大权值，但是这个做法很不优雅，我们将这个做法尝试拓展到没有特殊性质 B 的时候，会发现一个问题：当权值变为动态时，查询一个压位集合中的“权值最大值”是比较困难的，我们没法从一个没有特殊性质的集合里面提取权值的最值。

这个时候我们换一种思路：询问的信息相对固定，且询问的信息是最值类信息，因此我们按照权值从大到小加入点，同时对询问压位，每次把可以以这个点为最值的询问拿出来，标上答案，丢掉。

这个时候思路豁然开朗：对于 AB 性质，我们按照权值从大到小加入点 $y$ ，维护此时还没有找到最大值的询问，找到其中满足条件的：对“没有找到最大值的询问”、“询问区间包含编号 $a_{y}$ 的询问”、“可达 $y$ 的询问”求交，逐一标记即可！

可能某些特殊性质具有比较简单的做法，但是我们并不仅仅是为了解决它，而是为了探索这个性质下有什么东西能拓展到一般情况。

尝试拓展到没有 A 和 B 性质的情况：既然我们现在已经（离线地）以点为限制在考虑询问了，那么当点变化时，我们将变化前后的点在时间轴上拆分。

对于动态问题，建立时间轴 $T$ ，提前与处理每个点权值的变化，找到 $O (n + q)$ 组 $(y, T l, T r, a, b)$ ：“点 $y$ ”的权值在时间 $[T l, T r]$ 内标号为 $a$ ,权值为 $b$ ” 的五元组，我们在找到这些五元组后，仍然按权值从大到小加入这些五元组，每次找到可以以这个时间段的这个点为最值的询问，即对“没有找到最大值的询问”、“询问区间包含编号 $a$ 的询问”、“可达 $y$ 的询问”、“时间在 $[T l, T r]$ 的询问”求交，逐一标记即可！

我们之所以敢这么做的底气是，我们使用压位来处理这种“满足多个限制的对象的交”问题，因此多个限制维度不会增大时间复杂度，只会有乘常数的影响。（独立各维度了）

多限制问题，在时间能接受的情况下，使用压位可以独立化各维度的限制，因此添加新的限制维度对时间的影响是常数级别的。所以尽可能把限制都转移到“对于确定对象”上，不惜增加维度。

考虑实现：需要的东西都可以预处理，但是我们难以存下它们，因此将询问分 $B$ 个一组，一组一组做，做 $\frac{q}{B}$ 次即可，时间复杂度 $O (\frac{q ( n + q )}{w} + \frac{n q}{B})$ ，取 $B = 512$ 空间时间均可接受。

#include <bits/stdc++.h>
#define ll long long
#define All(x) x.begin(),x.end()
#define dout std::cerr<<"[DEBUG] "
#define rep(i,x,y) for(auto i(x);i<=(y);++i)
#define rrep(i,x,y) for(auto i(x);i>=(y);--i)
#define Debug(x) dout << #x << " = " << x << '\n'
 
const int N = 1e5 + 20 ;
const int L = 300  ;
 
int n , m , q ;
 
 
std :: bitset <N> reach[N] ;
std :: bitset <N> prel[N / L + 12] , sufr[N / L + 12] ;
 
 
struct Node {
	int id , a , b , tl , tr ;	
	Node (int _id = 0 , int _a = 0 , int _b = 0 , int _tl = 0 , int _tr = 0) {
		id = _id ;
		a = _a ;
		b = _b ;
		tl = _tl ;
		tr = _tr ;
	}
} ;
inline bool cmp (Node lef ,Node rig) {
	return lef.b < rig.b ; 
}
 
std :: vector <Node> event;
int last[N] ;
std :: vector <int> e[N] ;
std :: bitset <N> unc ; 
int ans[N] ;
 
std :: vector < std :: pair < int , int > > lv , rv ;
 
struct Query {
	int ql , qr , id ; 
} ;
 
std :: vector <Query> qs ;
 
int a[N] , b[N] ;
bool isq[N] ;
 
int sz ; 
 
inline void Assigna (int x,int c,int tim) {
	event.emplace_back (x , a[x] , b[x] , last[x] + 1 , tim) ;
	last[x] = tim ;
	a[x] = c ;
}
inline void Assignb (int x,int c,int tim) {
	event.emplace_back (x , a[x] , b[x] , last[x] + 1 , tim) ;
	last[x] = tim ;
	b[x] = c ;
}
 
void Clear() {
	lv.clear() ;
	rv.clear() ;
	memset (last , 0 ,sizeof last) ;
	memset (a , 0 ,sizeof a) ;
	memset (b , 0 ,sizeof b) ;
	memset (isq , 0 ,sizeof isq) ;
	memset (ans , 0 ,sizeof ans) ;
	unc = 0 ;
	qs.clear () ;
	event.clear() ;
	rep (i,0,N -1)
		e[i].clear ()  , reach[i] = 0 ;
	rep (i,0,N/L+2) 
		prel[i] = sufr[i] = 0 ;
}
inline std :: bitset <N> Qpre (int x) {
	x = std :: upper_bound (All (lv) , std::make_pair(x,N+1)) - lv.begin() - 1 ;
	std :: bitset <N> res ;
	int block = x / L ; 
	if (block) {
		res = prel[block - 1] ;
	}
	for (int i = block * L ; i <= x ; ++ i) {
		res[lv[i].second] = 1 ;
	}
	return res ;
}
 
inline std :: bitset <N> Qsuf (int x) {
	x = std :: upper_bound (All (rv) , std::make_pair(x,N+1)) - rv.begin() - 1 ;
	std :: bitset <N> res ;
	int block = x / L ; 
	if (block) {
		res = sufr[block - 1] ;
	}
	for (int i = block * L ; i <= x ; ++ i) {
		res[rv[i].second] = 1 ;
	}
	return res ;
}
 
void Main () {
	Clear () ;
	std :: cin >> n >> m >> q ;
	rep (i,1,m) {
		int u , v ;
		std :: cin >> u >> v;
		e[u].emplace_back (v) ;
	}
	rep (i,1,n) {
		std :: cin >> a[i] ;
	}
	rep (i,1,n) {
		std :: cin >> b[i] ;
	}
	rep (i,1,q) {
		int op ; 
		std :: cin >> op ;	
		if (op == 1) {
			int x , y ;
			std :: cin >> x >> y; 
			int ay = a[y] , ax = a[x] ;
			Assigna (x , ay , i) ;
			Assigna (y , ax , i) ;
		} 
		if (op == 2) {
			int x , y ;
			std :: cin >> x >> y ;
			int by = b[y] , bx = b[x] ;
			Assignb (x , by , i) ;
			Assignb (y , bx , i) ;
		}
		if (op == 3) {
			unc[i] = 1; 
			int node = 0 ; 
			qs.emplace_back(Query()) ;
			std :: cin >> node >> qs.back().ql >> qs.back().qr ; 
			reach[node][i] = 1 ;
			qs.back () .id = i ;	
			isq[i] = 1 ;
		}
	}
 
 
	rep (i,1,n) {
		if (last[i] != q) {
			event.emplace_back (i , a[i] , b[i] , last[i] + 1 , q) ;
		}
	}
 
 
 
 
	for(auto [ql , qr , id] : qs) {
		lv.emplace_back (ql , id) ;
		rv.emplace_back (n + 1 - qr , id) ;
	} 
 
	std :: sort (All (lv)) ;
	std :: sort (All (rv)) ;
 
 
	sz = lv.size() ;
 
	lv.emplace(lv.begin() , 0, 0) ;
	rv.emplace(rv.begin() , 0, 0) ;
 
	rep (i,1,sz) {
		prel[i / L][lv[i].second] = 1 ;
		sufr[i / L][rv[i].second] = 1 ;
	}
 
	rep (i,1,sz/L+1) {
		prel[i] |= prel[i - 1] ;
		sufr[i] |= sufr[i - 1] ;
	}
 
 
	rep (u,1,n) {
		for (int v : e[u]) {
			reach[v] |= reach[u] ;
		}
	}
 
	std :: sort (All (event) , [&](Node u,Node v){return u.b > v.b;}) ;	
 
	for (auto [u , a , b , tl , tr] : event) {
		auto B = reach[u] & unc & Qpre(a) & Qsuf(n + 1 - a) ; 
		for (int i = B._Find_next (tl - 1) ; i <= tr ; i = B._Find_next(i)) {
			unc[i] = 0 ;
			ans[i] = b ; 
		}
	} 
 
	rep (i,1,q) {
		if (isq[i]) {
			std :: cout << ans[i] << '\n' ;
		}
	}
 
}
 
signed main () {
 
	std :: ios :: sync_with_stdio (false) ;
	std :: cin.tie (0) ;
	std :: cout.tie (0) ;
	int c , T ;
	std :: cin >> c >> T ;
	while (T --)
		Main () ;
}

后记

我该在哪里停留？我问我自己。

——一直游到海水变蓝，她答道。

[OI题解] P11831 [省选联考 2025] 追忆

题意

Keywords & Evaluation

给思维剪枝

从特殊性质说起我们的思维过程

后记

评论

写下你的评论