题解：P8441 旭日东升

LXcjh4998 · 2026-08-07 14:56:07 · 题解

感觉大家写的 ODT 都太冗长了，提供一种不用大量分讨的写法，思路请去别的题解查看。

首先先插入区间 [-1,-1]。

我们希望能直接找到所有需要删去的区间 [L,R]，避免大量分讨。

注意到即条件 l-1\le R 且 L\le r+1。

可以用 upper_bound 找到第一个左端点大于 r+1 的区间，记该迭代器为 itr。

用 lower_bound 找到第一个左端点大于等于 l 的区间，判断其前驱是否满足条件，并记最终的迭代器为 itl。

很容易得到要插入区间的真实左右端点。

删去 [itl,itr] 的贡献，加入 itr 的新贡献，删去 [itl,itr) 这段迭代器，最后加入插入区间的贡献即可。

struct ODT{
    set<array<int,2>> odt;
    ODT(){odt.insert({-1,-1});}
    void assign(int l,int r,int v){
        auto itl=odt.lower_bound({l,0}),itr=odt.upper_bound({r+1,0});
        if(l-1<=(*prev(itl))[1])itl=prev(itl);
        int L=min(l,itl!=odt.end()?(*itl)[0]:INF),R=max(r,(*prev(itr))[1]);
        for(auto it=itl;it!=itr;++it)CDQ.addu((*prev(it))[1],(*it)[0],(*it)[1],-v);
        if(itr!=odt.end())CDQ.addu((*prev(itr))[1],(*itr)[0],(*itr)[1],-v),CDQ.addu(R,(*itr)[0],(*itr)[1],v);
        odt.erase(itl,itr);CDQ.addu((*prev(odt.insert({L,R}).first))[1],L,R,v);
    }
}ODT[N];