专栏文章

P11831 [省选联考 2025] 追忆

GGenius_Star影
P11831题解参与者 10已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miq3jchi
此快照首次捕获于
2025/12/03 22:22
3 个月前
此快照最后确认于
2025/12/03 22:22
3 个月前
查看原文

思路：

注意到空间和时间挺大的，考虑直接 O(n2ω)O(\frac{n^2}{\omega}) 求出每个点可达的 bitset fxf_x。
对于询问，我们想要知道 ai∈[l,r]a_i \in [l, r] 的 ii 的 bitset。
考虑建一个 BB 层的线段树，维护区间 ai∈[l,r]a_i \in [l, r] 的 bitset，注意这里我们不用 pushup，即单点修改时，直接从叶子到根修改一遍，复杂度为 O(B)O(B)；查询时，我们会进行至多 BB 次 bitset 的合并，以及 O(n2B)O(\frac{n}{2^B}) 的散点暴力。
现在我们已经支持 O(B)O(B) 的修改，O(Bnω+n2B)O(B\frac{n}{\omega} + \frac{n}{2^B}) 的区间查询 bitset。
我们将 ai∈[l,r]a_i \in [l, r] 的 ii 的 bitset 与 fuf_u 进行与运算得 f′f'，剩下的点就是合法的点，我们要找合法点中 bb 的最大值。
同样使用这种 BB 层的线段树维护 bi∈[l,r]b_i \in [l, r] 的 ii 的 bitset，然后在这个线段树上进行二分，若与 f′f' 与之后还有 11，这个 bb 就是存在的。
也至多进行 BB 次 bitset 的合并，最后暴力扫散点判断，二分复杂度为 O(Bnω+n2B)O(B \frac{n}{\omega} + \frac{n}{2^B})，取 B=4,5,6B = 4, 5, 6 时跑的快一些。
总时间复杂度为 O(Q(Bnω+n2B))O(Q(B\frac{n}{\omega} + \frac{n}{2^B}))。
先放一个赛后写的可能会被卡常的代码。

完整代码：

CPP
#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 1, B = 4, M = 17; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
struct Node{
	int l, r; 
	int dep;
	int lson, rson;
	bitset<N> s[2];
}X[M];
bitset<N> Ans;
int c, rt, T, n, m, q, u, v, op, x, y, l, r, cnt, ans;
int a[N], b[N], pa[N], pb[N];
bitset<N> f[N];
vector<int> E[N];
inline void add(int u, int v){
	E[u].push_back(v); 
}
inline void build(int &k, int l, int r, int dep){
	if(dep >= B)
	  return ;
	k = ++cnt;
	X[k].l = l, X[k].r = r;
	X[k].dep = dep;
	X[k].s[0].reset(), X[k].s[1].reset();
	if(l == r)
	  return ;
	int mid = (l + r) >> 1;
	build(X[k].lson, l, mid, dep + 1);
	build(X[k].rson, mid + 1, r, dep + 1);
}
inline void update(int k, int i, int v, bool f, int pre = 0){
	if(X[k].dep >= B)
	  return ;
	if((f ? b[v] : a[v]) < X[k].l || (f ? b[v] : a[v]) > X[k].r)
	  X[k].s[f][pre] = 0;
	X[k].s[f][v] = 1;
	if(X[k].l == X[k].r)
	  return ;
	int mid = (X[k].l + X[k].r) >> 1;
	if(i <= mid)
	  update(X[k].lson, i, v, f, pre);
	else
	  update(X[k].rson, i, v, f, pre);
}
inline void ask(int k, int l, int r){
	if(X[k].l == l && r == X[k].r){
		Ans |= X[k].s[0];
		return ;
	}
	if(X[k].dep == B - 1){
		for(int i = l; i <= r; ++i)
		  Ans[pa[i]] = 1;
		return ;
	}
	int mid = (X[k].l + X[k].r) >> 1;
	if(r <= mid)
	  ask(X[k].lson, l, r);
	else if(l > mid)
	  ask(X[k].rson, l, r);
	else{
		ask(X[k].lson, l, mid);
		ask(X[k].rson, mid + 1, r);
	}
}
inline int ask(int k){
	if(X[k].dep == B - 1){
		for(int i = X[k].r; i >= X[k].l; --i)
		  if(Ans[pb[i]])
		    return i;
		return 0;
	}
	if(X[k].l == X[k].r)
	  return X[k].l;
	if((Ans & X[X[k].rson].s[1]).count())
	  return ask(X[k].rson);
	else
	  return ask(X[k].lson);
}
inline void solve(){
	cnt = 0;
	n = read(), m = read(), q = read();
	for(int i = 1; i <= n; ++i){
		E[i].clear();
		f[i].reset();
		f[i][i] = 1;
	}
	while(m--){
		u = read(), v = read();
		add(v, u);
	}
	for(int u = n; u >= 1; --u)
	  for(auto v : E[u])
	    f[v] |= f[u];
	for(int i = 1; i <= n; ++i)
	  a[i] = read();
	for(int i = 1; i <= n; ++i)
	  b[i] = read();
	build(rt, 1, n, 0);
	for(int i = 1; i <= n; ++i){
		update(rt, a[i], i, 0);
		update(rt, b[i], i, 1);
		pa[a[i]] = i, pb[b[i]] = i;
	}
	while(q--){
		op = read();
		if(op == 1){
			x = read(), y = read();
			if(x == y)
			  continue;
			update(rt, a[x], y, 0, x);
			update(rt, a[y], x, 0, y);
			swap(a[x], a[y]);
			swap(pa[a[x]], pa[a[y]]);
		}
		else if(op == 2){
			x = read(), y = read();
			if(x == y)
			  continue;
			update(rt, b[x], y, 1, x);
			update(rt, b[y], x, 1, y);	
			swap(b[x], b[y]);
			swap(pb[b[x]], pb[b[y]]);		
		}
		else{
			Ans.reset(); 
			ans = 0;
			u = read(), l = read(), r = read();
			ask(rt, l, r);
			Ans &= f[u];
			if(Ans.count()){
				write(ask(rt));
				putchar('\n');
			}
			else
			  puts("0");
		}
	}
}
bool End;
int main(){
	//open("A.in", "A.out");
	c = read(), T = read();
	while(T--)
	  solve();
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...