[COCI 2010/2011 #7] UPIT

ID: 7461

远端评测题

1000ms

128MiB

尝试: 0

已通过: 0

难度: 8

上传者:

Hydro

标签>

2010

分块

COCI（克罗地亚）

Background

Mirko is tired of implementing different data structures for different tasks. So, he decided to write one ultimate data structure to handle his favorite sequence of numbers.

Come and help him!

Mirko will give you his sequence, as well as a series of operations you must perform. Each query either asks for information about the sequence or modifies the existing sequence. All possible operation types are listed below.

Query type	Description	Example
`1 A B X`	Change all elements in $[A,B]$ to $X$	$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $1$ $3$ $5$ $0$ $\to$ $(9, 8, 0, 0, 0, 4, 3, 2, 1)$
`2 A B X`	Increase all elements in $[A,B]$ by a value: position $A+k$ increases by $(k+1) \times X$	$(9, 8, 7, 6, 5, 4, 3, 2, 1)\to$ $2$ $3$ $5$ $2$ $\to (9, 8, 9, 10, 11, 4, 3, 2, 1)$
`3 C X`	Insert a number with value $X$ before the original position $C$	$(9, 8, 7, 6, 5, 4, 3, 2, 1)$ $\to$ $3$ $4$ $100$ $\to$ $(9, 8, 7, 100, 6, 5, 4, 3, 2, 1)$
`4 A B`	Query the sum of values in $[A,B]$	$(2, 18, 7, 6, 1, 4, 7, 7, 2)$ $\to$ $4$ $6$ $7$ $\to$ $result: 11$

Problem Description

Given a sequence $f$ , the following operations are supported.

Let the current length of the sequence be $n$ .

Query type	Description
`1 A B X`	$f_i = X (A \le i \le B)$ .
`2 A B X`	$f_i += (i - A + 1) \times X (A \le i \le B)$ .
`3 C X`	$f_{i+1} = f_i (C \le i \le n)$ , $f_C = X$ .
`4 A B`	Compute $\sum^B_{i=A} f_i$ .

Input Format

The first line contains two positive integers $n$ and $Q$ , representing the initial length of the sequence and the number of operations.

The second line contains $n$ non-negative integers, representing the initial sequence.

The next $Q$ lines each contain one query as described above.

Output Format

For each type $4$ operation, output one line with the answer.

4
0
25

Hint

Constraints

Let the current sequence length be $t$ .

For $100\%$ of the testdata: $1 \le n, Q \le 1 \times 10^5$ , $f_i \le 1 \times 10^5$ , $1 \le X \le 100$ , $1 \le A \le B \le t$ , $1 \le C \le t + 1$ .

Notes

This problem is worth $130$ points in total.

Translated from COCI2010-2011 CONTEST #7 T6 UPIT.

Translated by ChatGPT 5

#P6707. [COCI 2010/2011 #7] UPIT