[CodeForces] 444 C DZY Loves Colors 선분 트 리

C. DZY Loves Colors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
DZY loves colors, and he enjoys painting.
On a colorful day, DZY gets a colorful ribbon, which consists ofn units (they are numbered from 1 to n from left to right). The color of thei-th unit of the ribbon is i at first. It is colorful enough, but we still consider that the colorfulness of each unit is0 at first.
DZY loves painting, we know. He takes up a paintbrush with colorx and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of uniti currently is y. When it is painted by this paintbrush, the color of the unit becomesx, and the colorfulness of the unit increases by|x - y|.
DZY wants to perform m operations, each operation can be one of the following:

Paint all the units with numbers between l and r (both inclusive) with colorx.

Ask the sum of colorfulness of the units betweenl and r (both inclusive).

Can you help DZY?
Input
The first line contains two space-separated integersn, m (1 ≤ n, m ≤ 105).
Each of the next m lines begins with a integertype (1 ≤ type ≤ 2), which represents the type of this operation.
If type = 1, there will be3 more integers l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108) in this line, describing an operation1.
If type = 2, there will be2 more integers l, r (1 ≤ l ≤ r ≤ n) in this line, describing an operation2.
Output
For each operation 2, print a line containing the answer — sum of colorfulness.
Sample test(s)
Input

3 3
1 1 2 4
1 2 3 5
2 1 3

Output

8

Input

3 4
1 1 3 4
2 1 1
2 2 2
2 3 3

Output

3
2
1

Input

10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10

Output

129

Note
In the first sample, the color of each unit is initially[1, 2, 3], and the colorfulness is [0, 0, 0].
After the first operation, colors become [4, 4, 3], colorfulness become [3, 2, 0].
After the second operation, colors become [4, 5, 5], colorfulness become [3, 3, 2].
So the answer to the only operation of type 2 is 8.
전송 문: 【 CodeForces 】 444 C DZY Loves Colors
제목: n 길이 의 선분 을 드 리 겠 습 니 다. 왼쪽 에서 오른쪽으로 각각 1 ~ n 번 호 를 매 깁 니 다.처음에 선분 의 색깔 은 바로 그의 번호 이 고 처음에 모든 선분 의 증 가 는 0 이 었 다.
지금 당신 에 게 m 번 의 조작 을 드 리 겠 습 니 다. 조작 은 두 가지 로 나 눌 수 있 습 니 다.
1. L R x 는 구간 [L, R] 의 색 을 x 로 바 꾸 고 각 번호 가 i 인 단원 의 증분 에 abs (x - i) 를 더 합 니 다.
2. L R 조회 구간 [L, R] 에 있 는 모든 단원 의 증 가량 의 합.
(1 ≤ n, m ≤ 105), (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108)
제목 분석:
이 문제 에서 나의 방법 이 퇴화 될 지 모 르 겠 지만, 어쨌든 먼저 나의 방법 을 하나 주어 라.
두 개의 lazy 표 시 를 설정 합 니 다. 하나의 set [o] 는 현재 구간 범위 가 o 인 구간 내의 색 을 표시 합 니 다. 구간 내 가 단색 이면 set [o] 의 값 은 색상 값 과 같 습 니 다. 그렇지 않 으 면 set [o] = 0;아래로 전달 해 야 할 단위 의 증 가 를 나타 내 는 add [o] 태그
다시 sum [o] 를 설립 하면 구간 내의 증 량 과.
나 무 를 지 을 때 잎 이 맺 힌 set [o] = 자신의 번호, 다른 모든 것 은 0 이다.
라인 트 리 의 매번 업데이트 작업 L R x 에 대해 서 는 하위 구간 [l, r] 에 도 착 했 을 때 하위 구간 의 set [o] 가 0 이 아니라면 이 구간 이 단색 임 을 나타 내 며 직접 sum [o] + abs (x - set [o]) * (r - l + 1), add [o] + abs (x - set [o]), set [o] = x 를 사용 할 수 있 습 니 다. 모든 요소 가 같 기 때 문 입 니 다.증가 하 는 증 가 량 때문에 증가 하 는 증 가 량 은 아래로 전달 할 수 있다.만약 도착 한 하위 구간 [l, r] 시 하위 구간 의 set [o] = 0 은 하위 구간 내 에 적어도 두 가지 다른 색깔 이 있다 는 것 을 설명 한다. 그러면 증가 하 는 증 가량 이 다 르 고 전달 할 수 없 기 때문에 이때 만 나 는 하위 구간 의 set [o] 가 0 이 아니 라 는 것 을 계속 업데이트 할 수 밖 에 없다.
아버 지 를 위로 업데이트 할 때 주의 하 세 요. 만약 에 아버지 노드 의 두 부분 노드 의 set 값 이 같 으 면 아버지 노드 의 set 값 은 서브 노드 의 set 값 과 같 습 니 다. 다음 에 업데이트 할 때 아버지 노드 를 만나면 바로 돌아 갈 수 있 고 몇 걸음 더 걸 어서 서브 노드 까지 가지 않 아 도 됩 니 다.
다른 것 은 기본 적 인 선분 나무 와 다름없다.
PS: 제 코드 를 끊 을 수 있 는 데이터 가 있 을 것 같 습 니 다. 지나 가 는 신 이 제 코드 를 끊 을 수 있 는 지 증명 해 주 셨 으 면 좋 겠 습 니 다.대단히 감사합니다!
코드 는 다음 과 같 습 니 다:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define rt o , l , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define clear( a , x ) memset ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 100005 ;

int set[MAXN << 2] ;
LL sum[MAXN << 2] ;
LL add[MAXN << 2] ;

void pushUp ( int o , int l , int r ) {
	set[o] = ( set[ls] == set[rs] ? set[ls] : 0 ) ;
	sum[o] = sum[ls] + sum[rs] ;
}

void pushDown ( int o , int l , int r ) {
	int m = mid ;
	if ( set[o] ) set[ls] = set[rs] = set[o] ;
	if ( add[o] ) {
		sum[ls] += add[o] * ( m - l + 1 ) ;
		add[ls] += add[o] ;
		sum[rs] += add[o] * ( r - m ) ;
		add[rs] += add[o] ;
		add[o] = 0 ;
	}
}

void build ( int o , int l , int r ) {
	add[o] = set[o] = sum[o] = 0 ;
	if ( l == r ) {
		set[o] = l ;
		return ;
	}
	int m = mid ;
	build ( lson ) ;
	build ( rson ) ;
}

void update ( int x , int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) {
		if ( set[o] ) {
			add[o] += abs ( x - set[o] ) ;
			sum[o] += ( LL ) abs ( x - set[o] ) * ( r - l + 1 ) ;
			set[o] = x ;
			return ;
		}
	}
	pushDown ( rt ) ;
	int m = mid ;
	if ( L <= m ) update ( x , L , R , lson ) ;
	if ( m <  R ) update ( x , L , R , rson ) ;
	pushUp ( rt ) ;
}

LL query ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return sum[o] ;
	pushDown ( rt ) ;
	int m = mid ;
	LL ans = 0 ;
	if ( L <= m ) ans += query ( L , R , lson ) ;
	if ( m <  R ) ans += query ( L , R , rson ) ;
	return ans ;
}

void work () {
	int n , m ;
	int type , l , r , x ;
	while ( ~scanf ( "%d%d" , &n , &m ) ) {
		build ( root ) ;
		while ( m -- ) {
			scanf ( "%d%d%d" , &type , &l , &r ) ;
			if ( type == 1 ) {
				scanf ( "%d" , &x ) ;
				update ( x , l , r , root ) ;
			}
			else printf ( "%I64d
" , query ( l , r , root ) ) ;
		}
	}
}

int main () {
	work () ;
	return 0 ;
}