CF915E Physical Education Lessons（珂朵莉树）

中文题面

据说正解是动态开点线段树而且标记也不难下传的样子

然而这种区间推平的题目还是喜欢写珂朵莉树啊……码量小……

虽然真要构造的话随便卡……

 //minamoto

 #include<cstdio>

 #include<set>

 #include<iostream>

 #define IT set<node>::iterator

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int K=-,Z;

 inline void Ot(){fwrite(sr,,K+,stdout),K=-;}

 inline void print(int x){

     if(K><<)Ot();if(x<)sr[++K]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++K]=z[Z],--Z);sr[++K]='\n';

 }

 struct node{

     int l,r;mutable int v;

     node(int L,int R=-,int V=):l(L),r(R),v(V){}

     inline bool operator <(const node &b)const

     {return l<b.l;}

 };

 set<node> s;int sum;

 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,v=it->v;

     s.erase(it);

     s.insert(node(l,pos-,v?pos-l:));

     return s.insert(node(pos,r,v?r-pos+:)).first;

 }

 void assign(int l,int r,int v){

     IT itr=split(r+),itl=split(l);

     for(IT it=itl;it!=itr;++it) sum-=it->v;

     s.erase(itl,itr),s.insert(node(l,r,v*(r-l+)));

     sum+=v*(r-l+);

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     int n=read(),q=read();

     s.insert(node(,n+,));sum=n;

     while(q--){

         int l=read(),r=read();

         assign(l,r,read()-);

         print(sum);

     }

     return Ot(),;

 }