Skip to content

Commit 49049ae

Browse files
suisen-cpsuisen-cp
committed
Test of Lazy Segment Tree
1 parent 694ffe6 commit 49049ae

7 files changed

Lines changed: 669 additions & 0 deletions

File tree

‎LazySegTree/.gitignore‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
test/answer
2+
test/in
3+
test/out

‎LazySegTree/test/Gen.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
package test;
2+
3+
import java.io.File;
4+
import java.io.IOException;
5+
import java.io.PrintWriter;
6+
import java.util.Random;
7+
8+
public class Gen {
9+
static final int TESTCASE_NUM = 100;
10+
11+
static final Random rnd = new Random(System.nanoTime());
12+
13+
static final int N_MIN = 1;
14+
static final int N_MAX = 5000;
15+
static final int Q_MIN = 1;
16+
static final int Q_MAX = 10000;
17+
static final int A_MIN = -1000000000;
18+
static final int A_MAX = 1000000000;
19+
static final int V_MIN = -1000000000;
20+
static final int V_MAX = 1000000000;
21+
static final int QUERY_MIN = 0;
22+
static final int QUERY_MAX = 7;
23+
24+
public static void main(String[] args) {
25+
for (int i = 0; i < TESTCASE_NUM; i++) {
26+
String fileName = String.format("LazySegTree/test/in/testcase_%d", i);
27+
try (PrintWriter out = new PrintWriter(new File(fileName))) {
28+
gen(out);
29+
} catch (IOException e) {
30+
e.printStackTrace();
31+
System.exit(1);
32+
}
33+
}
34+
}
35+
36+
public static void gen(PrintWriter out) {
37+
final int N = rndIntClosedRange(N_MIN, N_MAX);
38+
final int Q = rndIntClosedRange(Q_MIN, Q_MAX);
39+
final int P_MIN = 0, P_MAX = N - 1;
40+
final int L_MIN = 0, L_MAX = N;
41+
final int R_MIN = 0, R_MAX = N;
42+
out.print(N); out.print(' '); out.print(Q); out.print('\n');
43+
final int[] A = new int[N];
44+
for (int i = 0; i < N; i++) {
45+
A[i] = rndIntClosedRange(A_MIN, A_MAX);
46+
out.print(A[i]);
47+
if (i < N - 1) {
48+
out.print(' ');
49+
} else {
50+
out.print('\n');
51+
}
52+
}
53+
for (int i = 0; i < Q; i++) {
54+
int type = rndIntClosedRange(QUERY_MIN, QUERY_MAX);
55+
out.print(type);
56+
if (type == 0) { // set
57+
int p = rndIntClosedRange(P_MIN, P_MAX);
58+
int v = rndIntClosedRange(V_MIN, V_MAX);
59+
out.print(' ');out.print(p);out.print(' ');out.print(v);out.print('\n');
60+
} else if (type == 1) { // apply
61+
int p = rndIntClosedRange(P_MIN, P_MAX);
62+
int v = rndIntClosedRange(V_MIN, V_MAX);
63+
out.print(' ');out.print(p);out.print(' ');out.print(v);out.print('\n');
64+
} else if (type == 2) { // apply
65+
int l = rndIntClosedRange(L_MIN, L_MAX);
66+
int r = rndIntClosedRange(R_MIN, R_MAX);
67+
int v = rndIntClosedRange(V_MIN, V_MAX);
68+
if (l > r) {
69+
int tmp = l; l = r; r = tmp;
70+
}
71+
out.print(' ');out.print(l);out.print(' ');out.print(r);out.print(' ');out.print(v);out.print('\n');
72+
} else if (type == 3) { // get
73+
int p = rndIntClosedRange(P_MIN, P_MAX);
74+
out.print(' '); out.print(p);out.print('\n');
75+
} else if (type == 4) { // prod
76+
int l = rndIntClosedRange(L_MIN, L_MAX);
77+
int r = rndIntClosedRange(R_MIN, R_MAX);
78+
if (l > r) {
79+
int tmp = l; l = r; r = tmp;
80+
}
81+
out.print(' ');out.print(l);out.print(' ');out.print(r);out.print('\n');
82+
} else if (type == 5) { // prodAll
83+
out.print('\n');
84+
} else if (type == 6) { // maxRight
85+
int l = rndIntClosedRange(L_MIN, L_MAX);
86+
int v = rndIntClosedRange(V_MIN, V_MAX);
87+
out.print(' ');out.print(l);out.print(' ');out.print(v);out.print('\n');
88+
} else if (type == 7) { // minLeft
89+
int r = rndIntClosedRange(R_MIN, R_MAX);
90+
int v = rndIntClosedRange(V_MIN, V_MAX);
91+
out.print(' ');out.print(r);out.print(' ');out.print(v);out.print('\n');
92+
} else {
93+
throw new AssertionError();
94+
}
95+
}
96+
}
97+
98+
public static int rndIntClosedRange(int l, int r) {
99+
return rnd.nextInt(r - l + 1) + l;
100+
}
101+
}

‎LazySegTree/test/Main.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package test;
2+
3+
public class Main {
4+
public static void main(String[] args) {
5+
test();
6+
}
7+
8+
static void test() {
9+
Gen.main(null);
10+
NaiveSolution.main(null);
11+
Solution.main(null);
12+
Test.main(null);
13+
}
14+
}

‎LazySegTree/test/NaiveSolution.java‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package test;
2+
3+
import java.io.File;
4+
import java.io.IOException;
5+
import java.io.PrintWriter;
6+
import java.util.Arrays;
7+
import java.util.Scanner;
8+
9+
public class NaiveSolution {
10+
static final int TEST_CASE_NUM = Gen.TESTCASE_NUM;
11+
public static void main(String[] args) {
12+
for (int i = 0; i < TEST_CASE_NUM; i++) {
13+
String inputFileName = String.format("LazySegTree/test/in/testcase_%d", i);
14+
String outputFileName = String.format("LazySegTree/test/answer/answer_%d", i);
15+
try (Scanner sc = new Scanner(new File(inputFileName))) {
16+
try (PrintWriter pw = new PrintWriter(new File(outputFileName))) {
17+
solve(sc, pw);
18+
sc.close();
19+
pw.flush();
20+
pw.close();
21+
}
22+
} catch (IOException e) {
23+
e.printStackTrace();
24+
System.exit(1);
25+
}
26+
}
27+
}
28+
29+
static final long INF = 1l << 60;
30+
31+
public static void solve(Scanner sc, PrintWriter pw) {
32+
final int N = Integer.parseInt(sc.next());
33+
final int Q = Integer.parseInt(sc.next());
34+
final long[] A = new long[N];
35+
Arrays.setAll(A, i -> Integer.parseInt(sc.next()));
36+
for (int i = 0; i < Q; i++) {
37+
int queryType = Integer.parseInt(sc.next());
38+
if (queryType == 0) {
39+
int p = Integer.parseInt(sc.next());
40+
int v = Integer.parseInt(sc.next());
41+
A[p] = v;
42+
} else if (queryType == 1) {
43+
int p = Integer.parseInt(sc.next());
44+
int v = Integer.parseInt(sc.next());
45+
A[p] += v;
46+
} else if (queryType == 2) {
47+
int l = Integer.parseInt(sc.next());
48+
int r = Integer.parseInt(sc.next());
49+
int v = Integer.parseInt(sc.next());
50+
for (int j = l; j < r; j++) {
51+
A[j] += v;
52+
}
53+
} else if (queryType == 3) {
54+
int p = Integer.parseInt(sc.next());
55+
pw.println(A[p]);
56+
} else if (queryType == 4) {
57+
int l = Integer.parseInt(sc.next());
58+
int r = Integer.parseInt(sc.next());
59+
long min = INF;
60+
for (int j = l; j < r; j++) {
61+
min = Math.min(min, A[j]);
62+
}
63+
pw.println(min == INF ? "INF" : min);
64+
} else if (queryType == 5) {
65+
long min = INF;
66+
for (int j = 0; j < N; j++) {
67+
min = Math.min(min, A[j]);
68+
}
69+
pw.println(min);
70+
} else if (queryType == 6) {
71+
int l = Integer.parseInt(sc.next());
72+
int v = Integer.parseInt(sc.next());
73+
for (int j = l; j <= N; j++) {
74+
if (j == N || A[j] <= v) {
75+
pw.println(j);
76+
break;
77+
}
78+
}
79+
} else if (queryType == 7) {
80+
int r = Integer.parseInt(sc.next());
81+
int v = Integer.parseInt(sc.next());
82+
for (int j = r; j >= 0; j--) {
83+
if (j == 0 || A[j - 1] <= v) {
84+
pw.println(j);
85+
break;
86+
}
87+
}
88+
} else {
89+
throw new AssertionError();
90+
}
91+
}
92+
}
93+
}

‎LazySegTree/test/Readme.md‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
# Test of Lazy Segment Tree
2+
3+
遅延評価セグメント木のテストです．
4+
5+
- `Gen.java` : テストケースを LazySegTree/test/in 内に生成します．
6+
- `NaiveSolution.java` : LazySegTree/test/in 内のテストを愚直に解いて，解答を LazySegTree/test/answer 内に生成します．
7+
- `Solution.java` : LazySegTree/test/in 内のテストを遅延評価セグメント木を用いて解いて，解答を LazySegTree/test/out 内に生成します．
8+
- `Test.java` : LazySegTree/test/answer 内の解答と LazySegTree/test/out 内の解答が一致しているかをテストします．
9+
- `Main.java` : `Gen.java`，`NaiveSolution.java`，`Solution.java`，`Test.java` を順に実行します．
10+
11+
## テスト概要
12+
13+
整数列 $A_0, \dots, A_{N-1}$ が与えられる．以下に示すクエリが合計 $Q$ 個与えられるので，順に処理する．
14+
15+
- `0 p v` : $a_p = v$ とする．
16+
- `1 p v` : $a_p$ に $v$ を加算する．
17+
- `2 l r v` : $a_l, \dots, a_{r-1}$ に $v$ を加算する．
18+
- `3 p` : $a_p$ の値を求めて出力する．
19+
- `4 l r` : $\min\{a_i\mid l\leq i \lt r\}$ を求めて出力する．但し，$l=r$ の場合は `INF` と出力する．
20+
- `5` : $\min\{a_i\mid 0\leq i \lt N\}$ を求めて出力する．
21+
- `6 l v` : $\max\{r\mid\min\{a_i\mid l\leq i \lt r\}\gt v\}$ を求めて出力する．但し，$a_l\leq v$ なら $l$ を出力する．
22+
- `7 r v` : $\min\{l\mid\min\{a_i\mid l\leq i \lt r\}\gt v\}$ を求めて出力する．但し，$a_{r-1}\leq v$ なら $r$ を出力する．
23+
24+
## 制約
25+
26+
- $1\leq N \leq 5000$
27+
- $1\leq Q \leq 10000$
28+
- $-10^9\leq A_i\leq 10^9$
29+
- $-10^9\leq v\leq 10^9$
30+
- $0\leq p\lt N$
31+
- $0\leq l\leq r\leq N$
32+
33+
## 入力
34+
35+
```math
36+
N Q
37+
A_{0} \dots A_{N-1}
38+
Query_{0}
39+
\vdots
40+
Query_{Q-1}
41+
```

0 commit comments

Comments
 (0)