题解 CF915E 【Physical Education Lessons】

SuperJvRuo

2018-10-03 17:31:00

Solution

最近做了很多珂朵莉树的题,一看这题区间赋值操作,直接上珂朵莉树。区间赋值成0和赋值成1都是珂朵莉树最简单的操作。 ``` #include<cstdio> #include<cctype> #include<set> int Read() { int x=0;char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } 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; } }; using std::set; set<node> s; int sum; #define IT set<node>::iterator IT split(int pos) { IT it=s.lower_bound(node(pos)); if (it!=s.end()&&it->l==pos) return it; --it; int L=it->l,R=it->r; int V=it->v; s.erase(it); s.insert(node(L,pos-1,V?pos-L:0)); return s.insert(node(pos,R,V?R-pos+1:0)).first; } void assign(int l,int r,int val) { IT itr=split(r+1),itl=split(l); for(IT it=itl;it!=itr;++it) { sum-=it->v; } s.erase(itl,itr); s.insert(node(l,r,val*(r-l+1))); sum+=val*(r-l+1); } int main() { register int n=Read(),q=Read(); s.insert(node(1,n,1)); sum=n; int l,r; while(q--) { l=Read(),r=Read(); assign(l,r,Read()-1); printf("%d\n",sum); } return 0; } ```