题解：P13983 数列分块入门 8

珂朵莉树是很棒的数据结构！
观察题目，发现每次询问后必须进行一次区间推平操作，这启示我们用珂朵莉树做这道题。
代码实现非常简单，拆分出区间后直接暴力遍历颜色段并累加贡献即可。

接下来进行复杂度分析：
设势能函数

\Phi

表示当前 ODT 中颜色段个数。显然初始势能

\Phi=n

。

split：每次最多新增 $1$ 个颜色段。
assign：两次 split 操作最多增加 $2$ 个颜色段。设操作的区间 $[l,r]$ 中有 $k$ 个颜色段，那么操作将删去 $k$ 个区间然后增加 $1$ 个区间。

综上，对于一次 assign 操作有

\Delta\Phi=2-(k-1)=3-k

。

那么，对于这

n

次操作，总体势能变化为：

\sum_{i=1}^n\Delta\Phi=\sum_{i=1}^n(3-k_i)=3n-\sum_{i=1}^n k_i

由于区间数量显然是正数，所以有：

n+\sum_{i=1}^n\Delta\Phi>0\\ n+3n-\sum_{i=1}^n k_i>0\\ \sum_{i=1}^n k_i<4n

回顾 assign 操作，设当前颜色段数为

m

，两次 split 操作时间复杂度

O(\log m)

，遍历

k

个颜色段时间复杂度

O(k)

，删除

k

个颜色段时间复杂度

O(k\log m)

，插入

1

个新颜色段复杂度

O(\log m)

，所以单次操作时间复杂度

O(k\log m)

。

根据前文，

\sum_{i=1}^n k_i<4n

，

m

不可能大于

n

。所以

\sum_{i=1}^n k_i

和

m

都是

O(n)

的。所以总时间复杂度就是：

\sum_{i=1}^n O(k_i\log m)=O(n\log n)

空间复杂度显然是线性。

关于时间复杂度的感性理解：我们发现每次操作若

k

很大，就会导致颜色段数急剧减少。而

k

极小时又不会产生过多的颜色段。所以给人的感觉就非常正确。

Code：

CPP

#include<cstdio>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x);
template<typename T,typename...Args>
void read(T &x,Args &...args);
struct node{
    int l,r,val;
    bool operator<(const node &x)const{
        return l<x.l;
    }
};
int n;
set<node> odt;
auto split(int pos){
    if(pos>n) return odt.end();
    auto it=odt.lower_bound({pos});
    if(it!=odt.end()&&it->l==pos)
        return it;
    it--;
    int l=it->l,r=it->r,val=it->val;
    odt.erase(it);
    odt.insert({l,pos-1,val});
    return odt.insert({pos,r,val}).first;
}
int assign(int l,int r,int c){
    int res=0;
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++)
        if(it->val==c) res+=it->r-it->l+1;
    odt.erase(itl,itr);
    odt.insert({l,r,c});
    return res;
}
int main(){
    read(n);
    for(int i=1,a;i<=n;i++)
        read(a),odt.insert({i,i,a});
    for(int i=1,l,r,c;i<=n;i++){
        read(l,r,c);
        printf("%d\n",assign(l,r,c));
    }
    return 0;
}

题解：P13983 数列分块入门 8

文章操作

相关推荐

评论

题解：P13983 数列分块入门 8