#P6936. 有向无环图

    ID: 6767 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-根号分块DAG 动态规划拓扑排序位集加速可达性离线查询

有向无环图

题目描述

给定一张有 nn 个点、mm 条边的有向无环图。每个点的点权初始为 00。需要依次执行 qq 次操作。

  • 1 u x:将从点 uu 能到达的所有点的点权设为 xx。
  • 2 u x:将从点 uu 能到达的所有点的点权改为原点权与 xx 的较小值。
  • 3 u:询问点 uu 的当前点权。

点 uu 本身也在它能到达的点集中。

输入格式

第一行三个正整数 n,m,qn,m,q。

接下来 mm 行,每行两个整数 u,vu,v,表示一条从 uu 到 vv 的有向边。

接下来 qq 行,每行是上述三种操作之一。

输出格式

对每个 3 u 操作,输出一行一个整数表示答案。

数据范围

1≤n,m,q≤1051\le n,m,q\le10^5,点的编号在 11 到 nn 之间,0≤x≤1090\le x\le10^9。原题时间限制 3 秒,内存限制 512 MB。

原题数据占比 附加限制
20% 1≤n,m,q≤50001\le n,m,q\le5000
另外 10% 无操作 1
无操作 2,且 1≤n,m,q≤500001\le n,m,q\le50000
另外 20% 无操作 2
1≤n,m,q≤500001\le n,m,q\le50000

原 PDF 题面