当前位置: 首页 > news >正文

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

\(\LARGE {P11831 [省选联考 2025] 追忆}\)

题解原出处

请阅读完彼题解再阅读此题解,此题解不对解题思路分析有帮助

仅仅提供代码上的解惑

我只是对他的代码进行了非常详细的注释处理,orz大佬


题意:

大哥图,考虑的是连通性和区间最大值维护 , bitset 闭包传递很好地解决连通性的问题
键值的交换直接进行 ; 权值的交换因为涉及 bitset 的更新 , 我们考虑记录下来 , 查询的时候再更新


\(\mathcal {Step\ 1:}\)初始化和图构建

// 读取测试用例数量
int testid, t; cin >> testid >> t; while(t--)// 清空邻接表,准备构建新图
for(int i = 1; i <= n; ++i) e[i].clear();// 构建有向图,e[u]存储u的所有出边邻居
for(int i = 1; i <= m; ++i)
{int u, v; cin >> u >> v;e[u].push_back(v); // 添加从u到v的有向边
}

\(\mathcal {Step\ 2:}\)数据初始化

// 读取每个节点的键值(用于后续查询)
for(int i = 1; i <= n; ++i) cin >> a[i];// 初始化权值系统和映射关系
// b[i]:节点i的权值
// wz1[b[i]] = i:权值b[i]对应的节点编号
// wz2[b[i]] = a[i]:权值b[i]对应的键值
for(int i = 1; i <= n; ++i) cin >> b[i], wz1[b[i]] = i, wz2[b[i]] = a[i];

\(\mathcal {Step\ 3:}\)bitset预处理

// 反图处理节点,确保依赖关系正确
for(int i = n; i >= 1; --i)
{// 清空当前节点的位集memset(bit[i], 0, sizeof(bit[i]));// 设置当前节点权值的位标记// b[i]>>6:确定在哪个64位块中// b[i]&63:确定在块中的具体位置(0-63)bit[i][b[i] >> 6] = (1llu << (b[i] & 63));// 合并所有后继节点的位集(可达性传播)for(int j : e[i]){for(int k = 0; k <= (n >> 6); ++k) bit[i][k] |= bit[j][k];}
}

\(\mathcal {Step\ 4:}\)查询处理核心逻辑

1: 交换键值

if(op == 1)
{cin >> x >> y;// 交换两个节点权值对应的键值映射swap(wz2[b[x]], wz2[b[y]]);
}

2: 交换权值

if(op == 2)
{cin >> x >> y;// 更新权值到节点的映射swap(wz1[b[x]], wz1[b[y]]);// 更新权值到键值的映射  swap(wz2[b[x]], wz2[b[y]]);// 记录交换历史,用于延迟更新xx[++tot] = b[x], yy[tot] = b[y];// 实际交换节点的权值swap(b[x], b[y]);
}

3: 查询操作(最复杂部分)

if(op == 3)
{cin >> x >> l >> r;// 延迟更新:处理所有未应用的交换操作while(pos[x] <= tot){// 检查交换涉及的权值在当前节点的位集中是否存在int a = (bit[x][xx[pos[x]] >> 6] >> (xx[pos[x]] & 63)) & 1;int b = (bit[x][yy[pos[x]] >> 6] >> (yy[pos[x]] & 63)) & 1;// 如果交换影响了当前节点的可达性,更新位集if(a != b){if(a == 0) {// 添加xx权值,移除yy权值bit[x][xx[pos[x]] >> 6] += (1llu << (xx[pos[x]] & 63));bit[x][yy[pos[x]] >> 6] -= (1llu << (yy[pos[x]] & 63));}else{// 移除xx权值,添加yy权值bit[x][xx[pos[x]] >> 6] -= (1llu << (xx[pos[x]] & 63));bit[x][yy[pos[x]] >> 6] += (1llu << (yy[pos[x]] & 63));}}++pos[x]; // 移动到下一个交换操作}// 执行实际查询bool flag = 0;// 从高位到低位遍历所有64位块for(int j = (n >> 6); j >= 0 && !flag; --j){if(bit[x][j] == 0) continue; // 跳过空块unsigned long long now = bit[x][j];// 遍历当前块中的所有设置位while(now != 0){// 计算具体的权值:块基址 + 位偏移int wz = (j << 6) + __lg(now);// 检查该权值对应的键值是否在查询范围内if(l <= wz2[wz] && wz2[wz] <= r){cout << wz << '\n'; // 输出满足条件的权值flag = 1;break;}// 移除当前处理的位,继续处理下一个now -= (1llu << __lg(now));}}if(!flag) cout << 0 << '\n'; // 无结果
}

算法核心思想

1. \(\textstyle \large 位集压缩‌:\)使用 unsigned long long 数组模拟大位集,每个元素管理64个权值
2. \(\textstyle \large‌ 延迟更新‌:\)交换操作不立即更新所有节点,而是记录历史,在查询时按需更新
3. \(\textstyle \large‌ 可达性传播‌:\)通过反向遍历确保子节点的信息正确传播到父节点
4. \(\textstyle \large‌ 高效查询‌:\)利用位运算快速检查权值存在性和范围条件


给出全部的代码

#include<bits/stdc++.h>
using namespace std;int n,m,q;
vector<int> e[100010];
int a[100010],b[100010];
unsigned long long bit[100010][(int)1e5/64+10];
int wz1[100010],wz2[100010];
int tot,xx[100010],yy[100010];
int pos[100010];int main()
{ios::sync_with_stdio(false),cin.tie(0);int testid,t; cin>>testid>>t; while(t--){cin>>n>>m>>q;for(int i=1; i<=n; ++i) e[i].clear();for(int i=1; i<=m; ++i){int u,v; cin>>u>>v;e[u].push_back(v);}for(int i=1; i<=n; ++i) cin>>a[i];for(int i=1; i<=n; ++i) cin>>b[i],wz1[b[i]]=i,wz2[b[i]]=a[i];for(int i=n; i>=1; --i){memset(bit[i],0,sizeof(bit[i]));bit[i][b[i]>>6]=(1llu<<(b[i]&63));for(int j:e[i]){for(int k=0; k<=(n>>6); ++k) bit[i][k]|=bit[j][k];}}tot=0;for(int i=1; i<=n; ++i) pos[i]=1;while(q--){int op,x,y,l,r; cin>>op;if(op==1){cin>>x>>y;swap(wz2[b[x]],wz2[b[y]]);}if(op==2){cin>>x>>y;swap(wz1[b[x]],wz1[b[y]]);swap(wz2[b[x]],wz2[b[y]]);xx[++tot]=b[x],yy[tot]=b[y];swap(b[x],b[y]);}if(op==3){cin>>x>>l>>r;while(pos[x]<=tot){int a=(bit[x][xx[pos[x]]>>6]>>(xx[pos[x]]&63)&1);int b=(bit[x][yy[pos[x]]>>6]>>(yy[pos[x]]&63)&1);if(a!=b){if(a==0){bit[x][xx[pos[x]]>>6]+=(1llu<<(xx[pos[x]]&63));bit[x][yy[pos[x]]>>6]-=(1llu<<(yy[pos[x]]&63));}else{bit[x][xx[pos[x]]>>6]-=(1llu<<(xx[pos[x]]&63));bit[x][yy[pos[x]]>>6]+=(1llu<<(yy[pos[x]]&63));}}++pos[x];}bool flag=0;for(int j=(n>>6); j>=0 && !flag; --j){if(bit[x][j]==0) continue;unsigned long long now=bit[x][j];while(now!=0){int wz=(j<<6)+__lg(now);if(l<=wz2[wz] && wz2[wz]<=r){cout<<wz<<'\n';flag=1;break;}now-=(1llu<<__lg(now));}}if(!flag) cout<<0<<'\n';}}}return 0;
}
http://www.hskmm.com/?act=detail&tid=37599

相关文章:

  • 2025-10-23 MX-S 模拟赛 赛后总结【MX】
  • PCL1.12 解决memory.h中EIGEN处中断问题
  • 完整教程:状态管理库 Zustand 的接入流程与注意点
  • 20251023
  • Java常用机制 - SPI机制详解
  • 塔吊施工环境与附属设施监测!思通数科 AI 卫士筑牢全场景安全防线
  • 采用opencv来识别信用卡的号码
  • 网络设备
  • 第二十二篇
  • 《程序员修炼之道:从小工到专家》阅读笔记1
  • 负载均衡及三种软件负载
  • 在 GEO / AIO 角度:如何优化 SEO 内容?
  • 多级多卡训练模型时有些参数没有参与loss计算和梯度更新的解决办法
  • 无题
  • Idea提高制作效率的快捷键最佳学习方式
  • rocky10自己手动换源
  • ski 和 db 模块的通信
  • 完整教程:ImmuCellAI 免疫浸润分析
  • 4.6.2版本来了!快来看看新版本有哪些改动
  • 2025-10-22 ZR-J 模拟赛 赛后总结【ZR】
  • P5285 [十二省联考 2019] 骗分过样例
  • Liferay Portal与DXP集合提供程序存在授权缺失漏洞分析
  • MapGIS Objects Java计算一条三维线段与一个三角形所在的平面的交点 - 教程
  • layui时间与日期选择器,时间范围查询数据,后端springboot
  • 读书笔记:OpenPBR 规范(2)
  • 轻量级图片信息解析程序
  • 2025.10.23 闲话-全局位运算 max 的解法
  • 习题-无限集与选择公理
  • Error: [WinError 10013] 以一种访问权限不允许的方式做了一个访问套接字的尝试及其解决方法
  • 项目管理软件是不是伪需求?