CF915E Physical Education Lessons

By Software Design

Luogu

\(n\) days (from from now to the end of the semester \(1\) to \(n\) number), they are all working days at the beginning. Next, the school staff will sequentially issue \(q\) instructions, each instruction can use three parameters \(l,r,k\) Description:

– If \(k=1\), then from \(l\) to \(r\) (including endpoints) all days become non-working days.

– if \(k=2\ ), then from \(l\) to \(r\) (including endpoints) All days become working days.

Help Alex count the number of remaining working days after each instruction is issued. 

#include#include#include#include#include#include#include#include< set>#define ll long long#define IT set::iteratorusing namespace std;inline int read(){ int x=0,o=1;char ch=getchar(); while(ch!='-' &&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')o=-1,ch=getchar(); while(ch>='0' &&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*o;}int sum;struct node{ int l,r;mutable int val; node(int L ,int R=-1,int V=0){l=L,r=R,val=V;} bool operator <(const node &x)const{ return ls; inline 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,val=it->val; s.erase(it); s.insert(node(l,pos-1,val)); return s.insert(node(pos, r,val)).first; }inline 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->val*(it->r-it->l+1); s.erase(itl,i tr); s.insert(node(l,r,val)); sum+=val*(r-l+1); }int main(){ int n=read(),m=read();sum= n; s.insert(node(1,n,1)); while(m--){ int l=read(),r=read(),opt=read(); if(opt==1){ assign(l,r,0); printf("%d\n",sum);} else{ assign(l,r,1); printf("%d\n",sum);}} return 0; }

, , , ,

Leave a Comment

Your email address will not be published.