题解 CF915E 【Physical Education Lessons】
SuperJvRuo
2018-10-03 17:31:00
最近做了很多珂朵莉树的题,一看这题区间赋值操作,直接上珂朵莉树。区间赋值成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;
}
```