CF915E Physical Education Lessons 珂朵莉树

问题描述

CF915E

LG-CF915E

---

题解

\(n \le 10^9\) 看上去非常唬人。

但是这种区间操作的题，珂朵莉树随便跑啊。

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){fh=-1;ch=getchar();	}

	else fh=1;

	while(ch>='0'&&ch<='9')	x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

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 <(node a)const{

		return l<a.l;

	}

};

#define IT set<node>::iterator

int n,T;

int l,r,k;

set<node>s;

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-1,V));

	return s.insert(node(pos,R,V)).first;

}

int ans;

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

	IT rr=split(r+1),ll=split(l);IT it=ll;

	for(;ll!=rr;ll++) ans-=ll->v*(ll->r-ll->l+1);

	s.erase(it,rr);s.insert(node(l,r,val));ans+=val*(r-l+1);

}

int main(){

	read(n);read(T);

	s.insert(node(1,n,1));ans=n;

	while(T--){

		read(l);read(r);read(k);--k;

		assign(l,r,k);

		printf("%d\n",ans);

	}

	return 0;

}