登录
中文
cover

JSC 2019 H. Distinct Integers

本文内容已上传星际文件存储系统「IPFS」,永久保存,不可删除。

ipfs

H. Distinct Integers

Discription

动态维护一个序列,每次支持单点修改,询问一组区间,返回这组区间的内部有多少子区间,满足所有数字均不相同。

Analysis

这种数据裸结构题怎么能不会呢。但是比赛时竟然无人通过!赛后 杜教 很威武的把这个 AK 了,不过点进 代码 居然一下子没有看懂。于是只好去瞄了一下 官方的题解 ....

二次元平面上に (i, bi) となる点をプロットしておきます条件をみたす部分列の個数を数えるクエリ (l, r) の答えを求めるためには,格子点 x, y (l ≤ x < r, l ≤ y ≤ x) であって,その左上領域に先程プロットした点を含まないもの個数を数えればいいです.すると,以下の疑似コードのような操作が高速に行えれば良いです.

void change(int i,int v){
    b[i] = v;
}

long long calc(int l,int r,int v){
    long long ans = 0;
    for(int i=l;i&lt;r;i++){
        v = max(v,b[i]);
        ans += v;
    }
    return ans;
}

こうすることで,この Segment Tree の更新が行えます.ここで重要なのは,sub(x, v) の計算が O(log(N)) 時間で行えることです.x が葉ノードの場合は自明です.次に,v ≤ mx(l(x)) の場合,sub(x, v) の値は,sub(l(x), v)cut(x) の値からわかります.次に,v > mx(l(x)) の場合ですが,この場合 l(x) の対応する区間の中では v が変化しないので,sub(l(x), v) の値は O(1) で計算できます.あとは,sub(r(x), v) を呼び出せば良いです.以上より,sub(x, v)O(log(N)) 回の再帰で計算できることになります.

Segment Tree の更新,および答え取得クエリににおいては,O(logN)sub を呼び出すことになるので,クエリあたり O(log2N) 時間で処理できることになります.するとこの問題は全体で O(NlogN + Qlog2N) 時間で解けます.

生词表:

  • プロット:Plot
  • 条件をみたす:满足条件的
  • クエリ:Query
  • 数を数える:Count the number
  • 答えを求めるためには:To find the answer
  • 疑似コード:Pseudo code
  • ノード:Node

我来解说一下。。大概意思就是。。。

设 bi 是左边第一个和 ai 相等的元素的下标。 在二维平面上所有的 (i, bi) 构成一条离散的折现,那么询问等价于 query 一个矩形中,所有在折线上方的点。伪代码就是上面给的那段。然后我们要做的就是用线段树去优化那段伪代码。

首先 mx(x) 表示 x 所在区间的 b 数组的最大值。
然后设 sub(x, v) 表示,上面那个 calc 函数,带入初始值 v 计算的结果。

能够 O(1) 的时间搞出 sub(x, v) 的就是普通的线段树了,只是询问的时候要按照从左到右的顺序进行递归,能 O(logN) 搞出来的话也还行,只是每次 query 的复杂度从 O(logN) 变成 O(log2N)。

所以剩下的关键就是考察 sub(x, v) 怎么计算。

分情况讨论,

  • 若 v >= mx[lx],等于 v * sz[lx] + sub(rx, v),左边直接算出。
  • 若 v <= mx[lx],那么等于 sub(lx, v) + sub(rx, mx[lx])。

我们注意到右边那个东西我们可以缓存起来(因为是单点修改),于是就做完了。怎么样,这个做法是不是似曾相识?没错,和 楼房重建那个题 如出一辙,而且应该要更容易想到。

杜教的写法 bi 是右边第一个和 ai 相等的元素的下标。所以 query 过程变成这样:

void change(int i,int v){
    b[i] = v;
}

long long calc(int l,int r,int v){
    long long ans = 0;
    for(int i=r-1;i>=l;i--){
        v = min(v, b[i]);
        ans += v;
    }
    return ans;
}

这样我们要先递归右子树,最后再减掉多出来梯形的面积即可。

本文发布于瞬matataki 未经授权禁止转载

免责声明:本文由用户「xiaodao」上传发布,内容为作者独立观点。不代表瞬Matataki立场,不构成投资建议,请谨慎对待。

分享
推荐
不推荐
0/500
1积分/条

评论 0

notContent

暂无内容