Codeforces 487E

题意

给你一张 \(n\) 个点 \(m\) 条边的无向图，每个点有点权，\(q\) 次操作

1. C a w，将第 \(a\) 个点的权值改为 \(w\)

2. A a b，询问 \(a\) 到 \(b\) 所有可能的简单路径上的点权最小值

简单路径即不经过一个点超过一次的路径

\(n,m,q\le 10^5\)

LOJ #2585

题意

在数轴上有\(n\)家商店，第\(i\)个商店有坐标\(x_i\)，种类\(t_i\in[1..k]\)，出现时间\([a_i,b_i]\)

有\(q\)组询问\(l_i,y_i\)，表示询问在时间\(y_i\)，离坐标\(l_i\)最远的商店类型到\(l_i\)的距离

类型\(t\)的商店到一个点的距离定义为所有存在的\(t\)类商店到这个点的距离的最大值

\(1\le n,q\le 3*10^5,1\le k\le n\)

\(1\le x_i,a_i,b_i\le 10^9\)

\(1\le l_i,y_i\le 10^8\)