AT_jag2018summer_day2_d Knapsack And Queries
题目描述
首先，给定一个正整数 $MOD$。
你有一个背包，初始时为空。
你需要执行 $Q$ 次查询。
- 在每次查询中，你需要先执行一个 `ADD` 或 `REMOVE` 操作，然后执行一个 `FIND` 操作。
- `ADD` 操作：给定正整数 $w, v$。将一个重量为 $w$、价值为 $v$ 的饼干放入背包。
- `REMOVE` 操作：从背包中取出重量最小的饼干并吃掉。
- `FIND` 操作：给定非负整数 $l, r$。你需要回答以下问题：
- 是否可以从背包中选择一些饼干，使得所选饼干的总重量 $X$ 满足 $l \leq (X\ {\rm mod}\ MOD) \leq r$？
- 如果不能，输出 `-1`。
- 否则，输出所选饼干的最大总价值。
输入格式
输入格式如下：
> $MOD$\
> $Q$\
> $t'_1$ $w'_1$ $v'_1$ $l'_1$ $r'_1$\
> $t'_2$ $w'_2$ $v'_2$ $l'_2$ $r'_2$\
> :\
> $t'_Q$ $w'_Q$ $v'_Q$ $l'_Q$ $r'_Q$
- $0 \leq t'_i, w'_i, v'_i, l'_i, r'_1 \leq 2^{30} - 1$
- 查询是**在线查询**。你可以通过解码 $t'_i, w'_i, v'_i, l'_i, r'_i$ 来获得 $t_i, w_i, v_i, l_i, r_i$。
- $t_i$ 表示查询类型。
- 当 $t_i = 1$ 时，执行 `ADD` 操作和 `FIND` 操作。
- 当 $t_i = 2$ 时，执行 `REMOVE` 操作和 `FIND` 操作。
- 当 $t_i = 2$ 时，你可以假定 $w_i=0$ 且 $v_i = 0$。
### 加密方式
我们提供了使用 C++11 (或更高版本)、Java、D、C# 编写的解密代码。
请使用 `class Crypto` 进行解密，`class Crypto` 的代码如下所示。
::::info[c++]
```cpp
#include //uint8_t, uint32_t
class Crypto {
public:
Crypto() {
sm = cnt = 0;
seed();
}
int decode(int z) {
z ^= next();
z ^= (next() > (i * 8));
}
for (int i = 0; i < 256; i++) {
data[i] = i;
}
I = J = 0;
int j = 0;
for (int i = 0; i < 256; i++) {
j = (j + data[i] + key[i%8]) % 256;
swap_data(i, j);
}
}
uint8_t next() {
I = (I+1) % 256;
J = (J + data[I]) % 256;
swap_data(I, J);
return data[(data[I] + data[J]) % 256];
}
};
```
::::
::::info[Java]
```java
public class Main {
public static class Crypto {
public Crypto() {
sm = cnt = 0;
seed();
}
public int decode(int z) {
z ^= next();
z ^= (next() (i * 8));
}
for (int i = 0; i < 4; i++) {
key[i+4] = (byte)(cnt >>> (i * 8));
}
for (int i = 0; i < 256; i++) {
data[i] = (byte)i;
}
I = J = 0;
int j = 0;
for (int i = 0; i < 256; i++) {
j = (j + asUint(data[i]) + asUint(key[i % 8])) % 256;
byte tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
int next() {
I = (I+1) % 256;
J = (J+asUint(data[I])) % 256;
byte tmp = data[I];
data[I] = data[J];
data[J] = tmp;
return asUint(data[(asUint(data[I]) + asUint(data[J])) % 256]);
}
}
public static void main(String[] args) {
...
}
}
```
::::
::::info[D]
```d
class Crypto {
public:
this() {
sm = cnt = 0;
seed();
}
int decode(int z) {
z ^= next();
z ^= (next() > (i*8));
}
foreach (i; 0..256) {
data[i] = cast(ubyte)(i);
}
I = J = 0;
int j = 0;
foreach (int i; 0..256) {
j = (j + data[i] + key[i%8]) % 256;
swap(data[i], data[j]);
}
}
ubyte next() {
I = (I+1) % 256;
J = (J + data[I]) % 256;
swap(data[I], data[J]);
return data[(data[I] + data[J]) % 256];
}
}
```
::::
::::info[C#]
```Csharp
class Crypto {
public Crypto() {
sm = cnt = 0;
data = new byte[256];
seed();
}
public int decode(int z) {
z ^= next();
z ^= (next() > (i*8));
}
for (int i = 0; i < 256; i++) {
data[i] = (byte)i;
}
I = J = 0;
int j = 0;
for (int i = 0; i < 256; i++) {
j = (j + data[i] + key[i%8]) % 256;
byte tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
byte next() {
I = (I+1) % 256;
J = (J + data[I]) % 256;
byte tmp = data[I];
data[I] = data[J];
data[J] = tmp;
return data[(data[I] + data[J]) % 256];
}
}
```
::::
解密过程如下：
- 首先，你需要创建一个 `class Crypto` 的实例。
- 对于每次查询，
- 依次调用 `decode` 函数，传入 $t', w', v', l', r'$，其返回值分别为 $t, w, v, l, r$。
- 使用 `FIND` 操作的结果调用 `query` 函数。
示例代码如下所示。
::::info[C++]
```cpp
#include
#include
#include //uint8_t, uint32_t
class Crypto {
...
};
int main() {
int MOD, Q;
scanf("%d %d", &MOD, &Q);
Crypto c;
for (int i = 0; i < Q; i++) {
int t, w, v, l, r;
scanf("%d %d %d %d %d", &t, &w, &v, &l, &r);
t = c.decode(t);
w = c.decode(w);
v = c.decode(v);
l = c.decode(l);
r = c.decode(r);
if (t == 1) {
(add candy(w, v))
} else {
(delete candy)
}
long long ans = (answer for query(l, r));
c.query(ans);
printf("%lld\n", ans);
}
}
```
::::
::::info[Java]
```Java
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
public static class Crypto {
...
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in); //!!warning!! : Java's scanner is slow
PrintWriter out = new PrintWriter(System.out);
int MOD = in.nextInt();
int Q = in.nextInt();
Crypto c = new Crypto();
for (int i = 0; i < Q; i++) {
int t, w, v, l, r;
t = c.decode(in.nextInt());
w = c.decode(in.nextInt());
v = c.decode(in.nextInt());
l = c.decode(in.nextInt());
r = c.decode(in.nextInt());
if (t == 1) {
(add candy(w, v))
} else {
(delete candy)
}
long ans = (answer for query(l, r));
c.query(ans);
out.println(ans);
}
out.flush();
}
}
```
::::
::::info[D]
```d
class Crypto {
...
}
int main() {
import std.stdio;
int MOD, Q;
readf("%d\n%d\n", &MOD, &Q);
Crypto c = new Crypto();
foreach (i; 0..Q) {
int t, w, v, l, r;
readf("%d %d %d %d %d\n", &t, &w, &v, &l, &r);
t = c.decode(t);
w = c.decode(w);
v = c.decode(v);
l = c.decode(l);
r = c.decode(r);
if (t == 1) {
(add candy(w, v))
} else {
(delete candy)
}
long ans = (answer for query(l, r));
c.query(ans);
writeln(ans);
}
return 0;
}
```
::::
::::info[C#]
```Csharp
using System;
using System.IO;
class Crypto {
...
}
class Myon {
static void Main() {
var writer = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false}; //fast writer
Console.SetOut(writer);
int MOD = int.Parse(Console.ReadLine());
int Q = int.Parse(Console.ReadLine());
Crypto c = new Crypto();
for (int i = 0; i < Q; i++) {
var inputs = Console.ReadLine().Split(' ');
int t, w, v, l, r;
t = c.decode(int.Parse(inputs[0]));
w = c.decode(int.Parse(inputs[1]));
v = c.decode(int.Parse(inputs[2]));
l = c.decode(int.Parse(inputs[3]));
r = c.decode(int.Parse(inputs[4]));
if (t == 1) {
(add candy(w, v))
} else {
(delete candy)
}
long ans = (answer for query(l, r));
c.query(ans);
Console.WriteLine(ans);
}
Console.Out.Flush();
}
}
```
::::
备注：
- 你不需要寻找此加密方法的漏洞。
- 当 $Q = 100,000$ 时，`class Crypto` 的运行时间最多约为 $200$ 毫秒。
输出格式
输出 `FIND` 操作的结果，每行一个。
说明/提示
**【样例解释1】**
解码此输入的结果如下。
```
10
7
1 5 10 5 5
2 0 0 0 9
1 7 10 2 4
1 12 11 9 9
2 0 0 1 1
1 22 10 2 3
1 32 100 4 4
```
| 背包 | 选定的饼干 |
|:----:|:---------:|
| (w, v) = {(5, 10)} | {(5, 10)} |
| {} | {} |
| {(7, 10)} | -1 |
| {(7, 10), (12, 11)} | {(7, 10), (12, 11)} |
| {(12, 11)} | -1 |
| {(12, 11), (22, 10)} | {(12, 11)} |
| {(12, 11), (22, 10), (32, 100)} | {(12, 11), (32, 100)} |
**【样例解释2】**
解码此输入的结果如下。
```
7
20
1 5 44 0 1
1 11 90 0 3
2 0 0 3 4
1 18 68 1 6
1 25 32 2 3
1 31 22 2 3
1 32 26 1 5
1 36 31 3 6
2 0 0 2 5
1 43 10 3 6
2 0 0 5 6
2 0 0 3 4
2 0 0 2 4
2 0 0 1 5
2 0 0 3 5
1 49 48 0 4
2 0 0 1 5
1 50 36 0 6
1 56 48 3 5
1 59 17 3 5
```
**【数据范围】**
- $2 \leq MOD \leq 500$
- $1 \leq Q \leq 100,000$
- $1 \leq w_i, v_i \leq 10^9$
- $0 \leq l_i \leq r_i \leq MOD-1$
- 每次 `ADD` 操作添加的饼干，其重量都严格大于此前任何 `ADD` 操作所添加的饼干。
- 执行 `REMOVE` 操作时，背包不为空。
- 查询是 **在线查询**。查询将按后续描述进行加密。