【讲课】8.8杂题选讲

菊开讲课,必属精品!


T1

题意

给你一个长度为 nn 的序列 aa 和一个常数 mm

定义 fl,xf_{l,x} 为区间 [l,l+m][l,l+m] 中小于 xx 的数的个数。

mm 组询问,每组询问给定 l,r,xl,r,x,询问 min{fi,x}(lir)\min\{f_{i,x}\}(l\leqslant i\leqslant r)

n,m105n,m\leqslant10^5

强制在线,空间 64MiB。

题解

分块,维护块内最大值

暂咕


T2

题意

有一棵 nn 个点的树,每条边有一个颜色黑或白,求有多少条路径,其中黑白边的数量满足 2×min(w,b)max(w,b)2\times\min(w,b)\geqslant\max(w,b)

n105n\leqslant10^5

题解

暂咕


T3

题意

天空中有 nn 朵云,第 ii 朵云出现的时间是 [li,ri][l_i,r_i],你可以用 cic_i 的代价使第 ii 朵云消失,你最多可以花费 CC 的代价,保证 CC 最多让两朵云消失,mm 次询问,第 ii 次询问从 00 时刻开始走,要走多久才能共经过 wiw_i 时间的无云区间。

n,m105n,m\leqslant10^5

题解

暂咕


T4

题意

给出一个长度为 nn 的不降序列 AA

求长度为 nn 的排列 BB,满足 min{ABiABi1}\min\{|A_{B_i}-A_{B_{i-1}}|\} 最大

n105,Ai109n\leqslant10^5,A_i\leqslant10^9

题解

暂咕


T5

题意

有一张 nn 个点 mm 条边的简单无向图,每条边上有一个正整数边权,ss 号点到 tt 号点的最短路长度为 LL。现在把 mm 条边中一些边的边权抹去,求出一组边的赋值方案使得最短路依旧是 LL

n,m5×105,L109n,m\leqslant5\times10^5,L\leqslant10^9

题解

暂咕


T6

题意

弑尽破净的第四分块

题解

咕咕咕


T7

题意

给你一个长度为 nn 的序列 aamm 次操作,每次操作在 ii 位置上放 cc 个球,并询问位置 yy 上有多少个球,然后把 xx 位置的球放到 axa_x 上去,强制在线。

n,m105n,m\leqslant10^5

题解

等价于在基环内向树上游走,环上可以开数组维护

树上有两种做法:

  1. 重链剖分后用堆维护每个元素到链顶的距离
  2. 二维线段树数子树内某一深度的点

T8

题意

nn 个数 w1,w2,,wnw_1,w_2,\ldots,w_n,求一个最大的 kk,使得能选出 kk 个数,使得它们模某个数 mm 相等,求出 kk 的最大值,并使 kk 最大的情况下 mm 尽量大。

m2,n105,wi107m\geqslant2,n\leqslant10^5,w_i\leqslant10^7

题解

随机选出一个数,这个数在答案集合中的概率是大于 12\frac 12 的。

暂咕


T9

题意

给你两个数 l,rl,r,求 lrl\sim r 除掉一个最大质因子后的最大质因子的和。

1lr10111\leqslant l\leqslant r\leqslant10^{11}

题解

Min_25 筛


T10

题意

给出一个 n×mn\times m 大小的矩阵,每个位置可以填 [1,c][1,c] 中的任意一个数,要求填完之后不能有两行或两列完全相同,求方案数。

n,m5000n,m\leqslant5000

题解

斯特林反演