第五届山东省ACM




D

类型: 线段树 区间更新

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q,T;

LL lazy[maxn];
LL sum[maxn];
bool flag[maxn];

void init(){
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
    memset(flag,false,sizeof(flag));
}

void PushDown(int p,int m){
    if(flag[p]){
        lazy[p<<1]=lazy[p<<1|1]=0;
        sum[p<<1]=sum[p<<1|1]=sum[p]=0;
        flag[p<<1]=flag[p<<1|1]=true;
        flag[p]=false;
    }
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

void setf(int p,int l,int r,int L,int R,int c){

    if(L<=l && r<=R){
        lazy[p]=0;
        sum[p]=0;
        flag[p]=true;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) setf(p<<1,l,mid,L,R,c);
    if(R>mid) setf(p<<1|1,mid+1,r,L,R,c);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

int main(){
    cin>>T;
    while(T--){
        init();
        scanf("%d%d",&N,&Q);
        int t,l,r,last=0;
        LL ans=0;
        for(int i=1;i<=Q;++i){
            scanf("%d%d%d",&t,&l,&r);
            ///先更新全部区间的值
            update(1,1,N,t-last,1,N);
            ///然后查询所需区间内的和
            ans+=Query(1,1,N,l,r);
            ///最后将所需区间内的值置为0
            setf(1,1,N,l,r,0);
            last=t;
        }
        printf("%lld\n",ans);
    }
    return 0;
}