Description

给定一个 nn 个点 mm 条边的有向带权图 (1n,m5×104)\left(1\leq n,m\leq5\times10^4\right) .
每条边以 (u,v,w)\left(u,v,w\right) (1w109)\left(1\leq w\leq10^9\right) 的形式给出。
定义一条路径的价值为该路径的长度,求第 kk (1k5×104)\left(1\leq k\leq5\times10^4\right) 小的价值。
qq (1q5×104)\left(1\leq q\leq5\times10^4\right) 次询问,共 tt (1t102)\left(1\leq t\leq10^2\right) 组测试。
保证 n,m,q,maxk2.5×105\sum n,\sum m,\sum q,\sum\max k\leq2.5\times10^5 ,保证 maxk\max k 合法。

Read More »

Description

给定一个长度为 nn 的序列 aa ,有 mm 次操作 (1n,m105)\left(1\leq n,m\leq10^5\right) .
序列 aa 满足 i[1,n], 1ain\forall i\in\left[1,n\right],\ 1\leq a_i\leq nij, aiaj\forall i\neq j,\ a_i\neq a_j .
操作分两种:

  • (1,pos)\left(1,pos\right) ,令 apos=apos+107a_{pos}=a_{pos}+10^7 .
  • (2,r,k)\left(2,r,k\right) ,求 min{x(i[1,r], aix)(xk)}\min\left\{x\big|\left(\forall i\in\left[1,r\right],\ a_i\neq x\right)\land\left(x\geq k\right)\right\} .

TT (1T10)\left(1\leq T\leq10\right) 组测试,保证 n5.1×105, m5.1×105\sum n\leq5.1\times10^5,\ \sum m\leq5.1\times10^5 .
操作参数 pos,r,kpos,r,k 分别为三个输入参数和 LastAnsLastAns 的异或值,保证合法。
第一次操作时,LastAns=0LastAns=0 .

Read More »