问题描述
题解
\(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;
}