TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

53.3% (8/15)

Submission's AC Ratio

15.7% (48/306)

Tags

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 a1,a2,,aN, w1,w2,,wN with length N.

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

  • change ai to any integer, this operation will cost you wi dollars.

Now, they will give you Q indepenedent queries. In the i-th query, they give you four integers Li,Ri,xi,yi. They want you to make the integers aLi,aLi+1,,aRi has z distinct integers, such that z[xi,yi]. 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 和小 B 最近發現一個酷酷的國王遊戲,他們想和你一起玩。

他們會給你兩個整數序列 a1,a2,,aN, w1,w2,,wN 長度皆為 N

你可以做以下操作任意多次(可以不做)

  • ai 改成任意整數 代價為 wi

現在,他們將對你詢問 Q(不同的詢問之間互相獨立 不影響)。 第 i 次詢問,會有四個整數 Li,Ri,xi,yi。目標是要讓 aLi,aLi+1,,aRi 中恰有 z 個不同的整數,其中 z[xi,yi]。同時因為他們很窮,所以希望你花越少代價越好

請寫一個程式幫幫他們計算答案 (最少需要花多少錢)

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 a1,a2,,aN.

The third line contains N integers w1,w2,,wN.

In the following Q lines, the i-th line indicates the i-th query. The i-th line contains four integers Li,Ri,xi,yi.

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

  • 1N,Q105
  • 1ai,wi105
  • 1LiRiN
  • 1xiyiRiLi+1

輸入第一行有兩個整數 N,Q, 分別代表序列的長度和詢問的數量

第二行有 N 個整數 a1,a2,,aN

第三行有 N 個整數 w1,w2,,wN

接下來 Q 行之中的第 i 行包含第 i 筆詢問,每行皆有四個整數 Li,Ri,xi,yi

各個參數的意義皆在題目中有解釋

  • 1N,Q105
  • 1ai,wi105
  • 1LiRiN
  • 1xiyiRiLi+1

Output Format

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

對於每筆詢問,請各自輸出一行整數代表答案

Sample Input 1

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

Sample Output 1

1
0
2
6

Hints

Problem Source

2021 台清交程式競賽 pK

Subtasks

No. Testdata Range Score
1 0~37 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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