题解

都有区间推平了怎么没有ODT呢

Code:

#include<bits/stdc++.h>
using namespace std;

// 定义节点结构体
struct Node{
    int l,r;
    mutable int v;
    Node(int l,int r=-1,int v=0):l(l),r(r),v(v){}
    bool operator<(const Node&o) const{
        return l<o.l;
    }
};
int n,m,l,r,c;
int ans[(int)2e5+1];
set<Node> odt;

// 分裂操作
inline auto split(const int &pos){
    auto it=odt.lower_bound(Node(pos));
    if(it!=odt.end()&&it->l==pos)return it;
    --it;
    int l=it->l,r=it->r,v=it->v;
    odt.erase(it);
    odt.insert(Node(l,pos - 1,v));
    return odt.insert(Node(pos,r,v)).first;
}

// 区间推平操作
inline void assign(const int &l,const int &r,const int &c){
    auto itr=split(r + 1),itl=split(l);
    odt.erase(itl,itr);
    odt.insert(Node(l,r,c));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    odt.insert(Node(1,n,0));
    for(int i=1;i<=m;i++){
        cin>>l>>r>>c;
        assign(l,r,c);
    }
    for(const auto&node:odt) for(int i=node.l;i<=node.r;i++) ans[i]=node.v;
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}