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 ;
}