【题目】

【题意】10^9范围的区间覆盖，至多3*10^5次区间询问。

【算法】线段树

【题解】每次询问至多增加两段区间，提前括号分段后线段树。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=1000010;struct tree{
    int l,r,delta,sum,p;}t[maxn*4];//int au[maxn],av[maxn],k[maxn],a[maxn],n,q,tot;set
          
           s;void build(int k,int l,int r){    t[k].l=l;t[k].r=r;t[k].delta=-1;    if(l==r){t[k].p=t[k].sum=a[l]-a[l-1];return;}    int mid=(l+r)>>1;    build(k<<1,l,mid);build(k<<1|1,mid+1,r);    t[k].p=t[k<<1].p+t[k<<1|1].p;    t[k].sum=t[k<<1].sum+t[k<<1|1].sum;}void modify(int k,int x){t[k].sum=t[k].p*x;t[k].delta=x;}void down(int k){    if(~t[k].delta){        modify(k<<1,t[k].delta);modify(k<<1|1,t[k].delta);        t[k].delta=-1;    }}void up(int k){t[k].sum=t[k<<1].sum+t[k<<1|1].sum;}void cover(int k,int l,int r,int x){    if(l<=t[k].l&&t[k].r<=r){modify(k,x);return;}    down(k);    int mid=(t[k].l+t[k].r)>>1;    if(l<=mid)cover(k<<1,l,r,x);    if(r>mid)cover(k<<1|1,l,r,x);    up(k);}int main(){    n=read();q=read();    for(int i=1;i<=q;i++){        au[i]=read();av[i]=read();k[i]=read();        s.insert(au[i]-1);s.insert(av[i]);    }    if(*s.begin()==0)s.erase(s.begin());    s.insert(n);    for(set
           
            ::iterator it=s.begin();it!=s.end();it++){ a[++tot]=*it; } for(int i=1;i<=q;i++){ au[i]=lower_bound(a+1,a+tot+1,au[i])-a; av[i]=lower_bound(a+1,a+tot+1,av[i])-a; } n=tot; build(1,1,n); for(int i=1;i<=q;i++){ cover(1,au[i],av[i],k[i]-1); printf("%d\n",t[1].sum); } return 0;}