记录编号	582059	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	4.496 s
提交时间	2023-09-01 21:02:31	内存使用	127.81 MiB

#include<bits/stdc++.h>
    using namespace std;
    int n,m,s;
    const int N=1e6*4;
    struct node{
        int L,R;
        long long sum,lazy=1;
    }t[N];
    long long a[N];
    void build(int p,int l,int r){
        t[p].L=l;
        t[p].R=r;
        if(l==r){
            t[p].sum=a[l];
            return ;
        }
        int mid=(l+r)/2;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        t[p].sum=t[p*2+1].sum+t[p*2].sum;
    }
    void spread(int p){
        if(!t[p].lazy){
            t[p*2].sum=(long long)t[p].lazy*(t[p*2].R-t[p*2].L+1);
            t[p*2].lazy=t[p].lazy;
            t[p*2+1].sum=(long long)t[p].lazy*(t[p*2+1].R-t[p*2+1].L+1);
            t[p*2+1].lazy=t[p].lazy;
            t[p].lazy=1;
        }
    }
    void change(int p,int l,int r,int c){
        if(t[p].L>=l&&t[p].R<=r){
            t[p].sum=(long long)c*(t[p].R-t[p].L+1); 
            t[p].lazy=c;
            return;
        }
        spread(p);
        int mid=(t[p].L+t[p].R)/2;
        if(l<=mid)change(p*2,l,r,c);
        if(r>mid)change(p*2+1,l,r,c);
        t[p].sum=t[p*2].sum+t[p*2+1].sum;
    }
    
    long long ask(int p,int l,int r){
    if(t[p].R<l||t[p].L>r){
        return 0;
        }
        if(l<=t[p].L&&r>=t[p].R){
            return t[p].sum;
        }
        spread(p);
        int mid=(t[p].L+t[p].R)/2;
        long long val=0;
        if(l<=mid){
              val+=ask(p*2,l,r);   
        }
        if(r>mid){
               val+=ask(p*2+1,l,r); 
        }
        return val; 
   }
    int main(){
        freopen("axis.in","r",stdin);
        freopen("axis.out","w",stdout);
          cin>>n;
          for(int i=1;i<=n;i++){
              a[i]=1;
          }
          build(1,1,n);
          cin>>m;
          for(int i=1;i<=m;i++){
              int l,r;
              cin>>l>>r;
              change(1,l,r,0);
              cout<<ask(1,1,n)<<endl;
          }
    }