洛谷 P11831 [省选联考 2025] 追忆

前置知识

  • 链式前向星存图
  • 拓扑排序
  • bitset 的基本用法
  • 卡常基本技巧

题意

给你一张 nn 个点 mm 条边的有向无环图。编号为 ii 的点有两个权值 aia_i ,bib_i。aa 和 bb 都是 11 到 nn 的排列。共有 qq 次操作,操作共有三种。

  1. 给定 xx,yy,交换 xx 号点和 yy 号点的 aa 权值。
  2. 给定 xx,yy,交换 xx 号点和 yy 号点的 aa 权值。
  3. 给定 xx,ll,rr,找出 xx 能够到达且 aa 权值在 [l,r][l,r] 的点中,bb 权值的最大值。

多组数据。

数据范围:T≤3T\le3,n≤105n\le 10^5,m≤2×105m\le 2\times 10^5,q≤105q\le 10^5。

时间限制 9.00s,空间限制 2.00GB。

做法

首先使用 bitset 求出每个点能到达的点的集合。

然后我们维护一个 mpimp_i 表示 bb 权值为 ii 的点的编号。

每一次查询,从大到小遍历 ii,如果 mpimp_i 在 [l,r][l,r] 范围内且 xx 能到达 mpimp_i,则 ii 就是答案,结束循环。

每一次修改,如果是改 aa,直接交换 axa_x 和 aya_y。如果是改 bb,交换完 bxb_x,byb_y 后还需要交换 mpbxmp_{b_x},mpbymp_{b_y}。

这样就能得到60分。(查询暴力遍历是20分)

卡常

  • 首先这道题不需要开 long long,所以删掉 #define int long long。

  • 然后链式前向星在 DAG 或树中比 vector 存图更加优秀 (同 P9755 [CSP-S 2023] 种树)

  • 交换两个变量时,使用 swap(a,b) 似乎比a^=b,b^=a,a^b 更优??实际测试中是这样的。

  • 关同步流,只使用 getchar,putchar 和 puts

然后就过了。

可能有评测姬波动,多交几发。

4 条评论

  • @ 2025-10-22 8:00:28

    我常常追忆过去。

    生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲,揉捻成天上朵朵白云。

    云朵之间亦有分别:积云厚重,而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀,而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦,太过清楚则无法愉悦自己的幻想,过分模糊却又坠入虚无。只有薄雾间的山水,面纱下的女子,那恰到好处的朦胧,才能满足我对美的苛求。

    追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友,推倒又重建的街道,种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来,我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间,在一个场景前驻足,在岁月的朦胧里瞭望过去的自己,感受尽可能多的甜蜜。美好的时光曾流过我的身体,我便心满意足。

    过去已经凝固,我带着回忆向前,只是时常疏于保管,回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

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

    • @ 2025-10-22 8:00:23

      你说得对但是

      考虑到评测机性能差距,本题较官方赛事增加了 3 秒的额外时限。

      • @ 2025-10-10 14:02:20

        哥们你纯唐

        • 1