FHVirus

50.0% (6/12)

16.4% (36/220)

# Description

Alice and Bob find out a new, cool king game to play, and they want to play the game with you. You will enjoy the game, right?

Alice and Bob will give you two integer sequences $a_1, a_2, \dots, a_N$, $w_1, w_2, \dots, w_N$ with length $N$.

Alice and Bob allow you to do the following operations for many(possibly zero) times:

• change $a_i$ to any integer, this operation will cost you $w_i$ dollars.

Now, they will give you $Q$ indepenedent queries. In the $i$-th query, they give you four integers $L_i, R_i, x_i, y_i$. They want you to make the integers $a_{L_i}, a_{L_i + 1}, \dots, a_{R_i}$ has $z$ distinct integers, such that $z \in [x_i, y_i]$. Also, since they are poor, they want you to spend as little as possible.

Please write a program to help them calculate the answers (minimum dollar that they have to spend).

• 把 $a_i$ 改成任意整數 代價為 $w_i$ 元

# Input Format

The first line of the input contains two integers $N, Q$, indicating the length of the sequences, and the number of queries.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$.

The third line contains $N$ integers $w_1, w_2, \dots, w_N$.

In the following $Q$ lines, the $i$-th line indicates the $i$-th query. The $i$-th line contains four integers $L_i, R_i, x_i, y_i$.

The meanings of the parameters above have been explained in the problem statement.

• $1 \leq N, Q \leq 10^ 5$
• $1 \leq a_i, w_i \leq 10^ 5$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq x_i \leq y_i \leq R_i - L_i + 1$

• $1 \leq N, Q \leq 10^ 5$
• $1 \leq a_i, w_i \leq 10^ 5$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq x_i \leq y_i \leq R_i - L_i + 1$

# Output Format

For each query, print the answer to the query in one line.

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

1
0
2
6

# Problem Source

2021 台清交程式競賽 pK

No. Testdata Range Score
1 0~37 100

# Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 7500 1024000 65536 1
1 7500 1024000 65536 1
2 7500 1024000 65536 1
3 7500 1024000 65536 1
4 7500 1024000 65536 1
5 7500 1024000 65536 1
6 7500 1024000 65536 1
7 7500 1024000 65536 1
8 7500 1024000 65536 1
9 7500 1024000 65536 1
10 7500 1024000 65536 1
11 7500 1024000 65536 1
12 7500 1024000 65536 1
13 7500 1024000 65536 1
14 7500 1024000 65536 1
15 7500 1024000 65536 1
16 7500 1024000 65536 1
17 7500 1024000 65536 1
18 7500 1024000 65536 1
19 7500 1024000 65536 1
20 7500 1024000 65536 1
21 7500 1024000 65536 1
22 7500 1024000 65536 1
23 7500 1024000 65536 1
24 7500 1024000 65536 1
25 7500 1024000 65536 1
26 7500 1024000 65536 1
27 7500 1024000 65536 1
28 7500 1024000 65536 1
29 7500 1024000 65536 1
30 7500 1024000 65536 1
31 7500 1024000 65536 1
32 7500 1024000 65536 1
33 7500 1024000 65536 1
34 7500 1024000 65536 1
35 7500 1024000 65536 1
36 7500 1024000 65536 1
37 7500 1024000 65536 1