【BZOJ4009】【HNOI2015】接水果

为什么这一道题被权限了啊 好气啊

题意就是,先给你若干条链,然后每次给你一条链问之前给的那些链里面是它子链的权值第\(k\)小的是多少。

可以想到,如果一条链是另一条的子链,那么可以按是否有一个点是另一个点父亲分两种情况。

那么我们写出对父链的约束条件,可以发现是一个类似矩阵的东西。

即把问题转化为:先给你若干个矩阵,每次问你覆盖某个点的矩阵中权值第\(k\)小的是多少。

于是用整体二分。计算点在多少矩阵内用扫描线+树状数组。

说点什么

您将是第一位评论人!

提醒
wpDiscuz