Loading...

CF915E 题解

check评论:0 条 remove_red_eye浏览量:190 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-09-02

珂朵莉树题目

看到区间赋值操作,就是裸的珂朵莉树了..

每次操作时查询有多少个工作日改为了非工作日即可

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
    bool v;
    node(int L,int R=-1,bool V=1):l(L),r(R),v(V){}
    bool operator<(const node&a)const
    {
        return l<a.l;    
    }    
};
set<node> st;
int n,m,ans;
#define IT set<node>::iterator
IT split(int pos)
{
    IT iter=st.lower_bound(node(pos));
    if(iter!=st.end()&&pos==iter->l)
    {
        return iter;
    }
    --iter;
    int L=iter->l,R=iter->r;
    bool V=iter->v;
    st.erase(iter);
    st.insert(node(L,pos-1,V));
    return st.insert(node(pos,R,V)).first;
}
void assign(int l,int r,bool v)
{
    IT itr=split(r+1),itl=split(l),itq;
    itq=itl;
    int nans=0,rans=0;
    while(itl!=itr)
    {
        if(itl->v==1)
        {
            nans+=(itl->r-itl->l+1);
        }
        ++itl;
    }
    st.erase(itq,itr);
    st.insert(node(l,r,v));
    if(v==1)
    {
        rans=(r-l+1);
    }
    ans-=(nans-rans);
}
int main()
{
    cin>>n>>m;
    ans=n;
    st.insert(node(1,n,1));
    st.insert(node(n+1,n+1,0));
    for(int i=1;i<=m;i++)
    {
        int l,r,opt;
        scanf("%d%d%d",&l,&r,&opt);
        opt--;
        assign(l,r,opt);
        printf("%d\n",ans);
    }
}

chevron_left 虚树 学习笔记
珂朵莉树笔记 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名