아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

홍준이는 색칠을 좋아해

시간 제한2초메모리 제한512 MB

요약
벽돌의 초기 색은 번호와 같고 색의 화려함은 0에서 시작한다. 구간을 한 색으로 칠하면 각 벽돌의 화려함이 색 변화의 절댓값만큼 늘어나며, 구간 합을 묻는 질의에 답한다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 구현, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

홍준이는 색칠을 좋아한다.

홍준이는 생일 선물로 벽돌 nn개를 받아 일렬로 늘어놓았다. 가장 왼쪽 벽돌이 1번이고, 오른쪽으로 갈수록 번호가 1씩 커져서 가장 오른쪽 벽돌이 nn번이다. 처음에 ii번 벽돌의 색은 ii번 색이고, 모든 벽돌의 다채도는 0이다.

홍준이는 연속한 벽돌 구간에 같은 색을 칠한다. ii번 벽돌의 현재 색이 yy인데 홍준이가 색 xx로 칠하면, 그 벽돌의 다채도는 ∣x−y∣|x-y|만큼 늘어나고 색은 xx가 된다.

홍준이는 작업을 mm번 한다. 작업은 다음 두 가지 중 하나다.

  1. LL번 벽돌부터 RR번 벽돌까지 색 XX로 칠한다.
  2. LL번 벽돌부터 RR번 벽돌까지의 다채도 합을 구한다.

홍준이를 도와주는 프로그램을 작성하시오.

입력

첫째 줄에 벽돌의 개수 nn과 작업의 수 mm이 주어진다. (1≤n,m≤100 0001 \le n, m \le 100\,000)

다음 mm개 줄에는 작업이 한 줄에 하나씩 주어진다. 각 줄은 작업의 종류를 나타내는 정수 TypeType(1 또는 2)으로 시작한다.

TypeType이 1이면 작업 1을 나타내는 정수 LL, RR, XX가 이어서 주어진다. (1≤L≤R≤n1 \le L \le R \le n, 1≤X≤100 000 0001 \le X \le 100\,000\,000)

TypeType이 2이면 작업 2를 나타내는 정수 LL, RR가 이어서 주어진다. (1≤L≤R≤n1 \le L \le R \le n)

출력

작업 2를 수행할 때마다 그 구간의 다채도 합을 한 줄에 하나씩, 작업 순서대로 출력한다.

예제5

  1. 예제 1

    입력
    3 4
1 1 3 4
2 1 1
2 2 2
2 3 3
    예상 출력
    3
2
1

  2. 예제 2

    입력
    1 3
2 1 1
1 1 1 100000000
2 1 1
    예상 출력
    0
99999999

  3. 예제 3

    입력
    5 7
1 1 5 10
2 1 5
1 2 4 10
2 1 5
1 1 5 10
2 1 5
2 3 3
    예상 출력
    35
35
35
7

  4. 예제 4

    입력
    6 9
2 1 6
1 2 5 3
2 1 6
1 1 3 7
2 1 3
2 4 6
1 4 6 1
2 1 6
2 5 5
    예상 출력
    0
4
15
3
27
4

  5. 예제 5

    입력
    4 4
2 1 4
2 1 1
2 2 3
2 4 4
    예상 출력
    0
0
0
0