sdut2880

3307 ワード

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>
typedef long long LL ;

const int N = 100008 ;

namespace SegTree{

    LL sum[N<<2] , Add[N<<2] , Set[N<<2] ;
    void  up(int t){
          sum[t] = sum[t<<1] + sum[t<<1|1] ;
    }

    void  down(int t , int l , int r){
          int m = (l + r) >> 1 ;
          if(Set[t] != -1){
               Set[t<<1] = Set[t] ;
               Add[t<<1] = 0 ;
               sum[t<<1] = Set[t] * (m - l + 1) ;

               Set[t<<1|1] = Set[t] ;
               Add[t<<1|1] = 0 ;
               sum[t<<1|1] = Set[t] * (r - m) ;

               Set[t] = -1 ;
          }

          if(Add[t]){
               Add[t<<1] += Add[t] ;
               sum[t<<1] += Add[t] * (m - l + 1) ;

               Add[t<<1|1] += Add[t] ;
               sum[t<<1|1] += Add[t] * (r - m) ;

               Add[t] = 0 ;
          }
    }

    void build(int t , int l , int r){
         Add[t] = 0 ;
         Set[t] = -1 ;
         sum[t] = 0 ;
         if(l == r) return ;
         int m = (l + r) >> 1 ;
         build(t<<1 , l , m) ;
         build(t<<1|1 , m+1 , r) ;
         up(t) ;
    }

    void doAdd(int t , int l , int r , int L , int R , LL c){
         if(L <= l && r <= R){
              Add[t] += c ;
              sum[t] += c * (r - l + 1) ;
              return ;
         }
         down(t , l , r) ;
         int m = (l + r) >> 1 ;
         if(L <= m) doAdd(t<<1 , l , m , L , R , c) ;
         if(R > m)  doAdd(t<<1|1 , m+1 , r , L , R , c) ;
         up(t) ;
    }

    void doSet(int t , int l , int r , int L , int R , LL c){
         if(L <= l && r <= R){
              Set[t] = c ;
              sum[t] = c * (r - l + 1);
              Add[t] = 0 ;
              return ;
         }
         down(t , l , r) ;
         int m = (l + r) >> 1 ;
         if(L <= m) doSet(t<<1 , l , m , L , R , c) ;
         if(R > m)  doSet(t<<1|1 , m+1 , r , L , R , c) ;
         up(t) ;
    }

    LL  ask(int t , int l , int r , int L , int R){
        if(L <= l && r <= R) return sum[t] ;
        down(t , l , r) ;
        int m = (l + r) >> 1 ;
        LL res = 0 ;
        if(L <= m) res += ask(t<<1 , l , m , L , R) ;
        if(R > m)  res += ask(t<<1|1 , m+1 , r , L , R) ;
        up(t) ;
        return res ;
    }
}


int main(){

    std::ios::sync_with_stdio(false) ;

    int t , n , m  , l , r , k , prek  ;
    scanf("%d" , &t) ;
    while(t--){
        scanf("%d%d" , &n , &m) ;
        SegTree::build(1 , 1 , n) ;
        prek = 0 ;
        LL res = 0LL ;
        while(m--){
            scanf("%d%d%d" , &k , &l , &r) ;
            SegTree::doAdd(1 , 1 , n , 1 , n , (LL)k - prek) ;
            res += SegTree::ask(1 , 1 , n  , l , r) ;
            SegTree::doSet(1 , 1 , n , l , r , 0LL) ;
            prek = k ;
        }
        std::cout<< res << std::endl ;
    }
    return 0 ;
}