---

  开胃小菜。

---

试题 A: 求和

本题总分：$5$ 分

---

【问题描述】

  求 $1$ （含）至 $20230408$ （含）中每个数的和。

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

204634714038436

---

自然数列求和，$1+2+\cdots +n=\frac{n(n+1)}{2}$。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        System.out.println(
                20230408 * (20230408 + 1l) / 2
        );
    }
}

或者迭代答案。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        long ans = 0;
        for (int i = 1; i <= 20230408; ++i)
            ans += i;
        System.out.println(ans);
    }
}

---

试题 B: 分糖果

本题总分：$5$ 分

---

【问题描述】

  两种糖果分别有 $9$ 个和 $16$ 个，要全部分给 $7$ 个小朋友，每个小朋友得到的糖果总数最少为 $2$ 个最多为 $5$ 个，问有多少种不同的分法。
  只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

5067671

---

观察到两种糖果组成二至五个的方案为 $3+4+5+6=18$ 种，以该方案为蓝本枚举 $7$ 个小朋友构成的总分配方案一共有 $18^7$ 种，时间复杂度显然不理想，于是考虑枝剪。
一个可以观察到的上界是 $C_{15}^6{C}_{22}^6\approx 3.7e8$，因为一个自然数 $n$ 被拆分成 $k$ 个非负整数根据插板法共有 $C_{n+k-1}^{k-1}$ 种方案。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int n = 7, c1 = 9, c2 = 16, l = 2, r = 5;

    long ans = 0;

    void dfs(int depth) {
        if (depth == n) {
            if (c1 == 0 && c2 == 0) ++ans;
        } else {
            for (int i = l; i <= r; ++i)
                for (int k = 0, g = i; k <= i; ++k, --g) {
                    if (c1 < k || c2 < g) continue;
                    c1 -= k;
                    c2 -= g;
                    dfs(depth + 1);
                    c1 += k;
                    c2 += g;
                }
        }
    }

    void run() {
        dfs(0);
        System.out.println(ans);
    }
}

---

试题 C: 三国游

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$10$ 分

---

【问题描述】

  小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 $X,Y,Z$ (一开始可以认为都为 $0$ )。游戏有 $n$ 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 $i$ 个事件发生时会分别让 $X,Y,Z$ 增加 $A_i,B_i,C_i$。
  当游戏结束时 (所有事件的发生与否已经确定)，如果 $X,Y,Z$ 的其中一个大于另外两个之和，我们认为其获胜。例如，当 $X>Y+Z$ 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
  如果不存在任何能让某国获胜的情况，请输出 $-1$。

【输入格式】

  输入的第一行包含一个整数 $n$。
  第二行包含 $n$ 个整数表示 $A_i$，相邻整数之间使用一个空格分隔。
  第三行包含 $n$ 个整数表示 $B_i$，相邻整数之间使用一个空格分隔。
  第四行包含 $n$ 个整数表示 $C_i$，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

3
1 2 2
2 3 2
1 0 7

【样例输出】

2

【样例说明】

  发生两个事件时，有两种不同的情况会出现获胜方。
  发生 $1,2$ 事件时蜀国获胜。
  发生 $1,3$ 事件时吴国获胜。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 500$；
  对于 $70\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^5，1\le A_i,B_i,C_i\le 10^9$。

---

贪心

---

同时考虑三个国家是相当困难的，于是考虑分别求出魏蜀吴分别获胜的话最大事件数，最优答案就是这若干个数中的最大值。
以魏举例，记第 $i$ 个事件对魏获胜的贡献为 $x_i-y_i-z_i$，按贡献降序重排事件，找到一个 $k$，满足 ${\sum }_{i=1}^k{x}_i>{\sum }_{i=1}^k(y_i+z_i)$ 且 $k$ 尽可能大，若 $k<n$，易知 ${\sum }_{i=1}^{k+1}{x}_i\le {\sum }_{i=1}^{k+1}(y_i+z_i)$ 且 $[1,k]$ 间的或 $(k,n]$ 间的事件交换不会对和式值造成影响，$[1,k]$ 间与 $(k,n]$ 间的元素交换会使 ${\sum }_{i=1}^{k+1}(x_i-y_i-z_i)$ 变小，不等式无法成立，从而 k 对魏来说最优。

import java.io.IOException;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.util.function.Function;
import java.util.Comparator;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    class Tuple {

        int x, y, z;
    }

    Tuple[] events;

    int greedy(Comparator<Tuple> comp, Function<long[], Boolean> func) {
        Arrays.sort(events, comp);
        long[] sum = new long[3];
        int res = -2;
        for (int i = 0; i < events.length; ++i) {
            sum[0] += events[i].x;
            sum[1] += events[i].y;
            sum[2] += events[i].z;
            if (func.apply(sum)) res = i;
        }
        return res + 1;
    }

    int max(int arg1, int arg2, int arg3) { return Math.max(arg1, Math.max(arg2, arg3)); }

    void run() {
        int n = nextInt();
        events = new Tuple[n];
        for (int i = 0; i < n; ++i) events[i] = new Tuple();
        for (int i = 0; i < n; ++i) events[i].x = nextInt();
        for (int i = 0; i < n; ++i) events[i].y = nextInt();
        for (int i = 0; i < n; ++i) events[i].z = nextInt();
        System.out.println(
                max(
                        greedy((a, b) -> Integer.compare(b.x - b.y - b.z, a.x - a.y - a.z), s->s[0] > s[1] + s[2]),
                        greedy((a, b) -> Integer.compare(b.y - b.x - b.z, a.y - a.x - a.z), s->s[1] > s[0] + s[2]),
                        greedy((a, b) -> Integer.compare(b.z - b.x - b.y, a.z - a.x - a.y), s->s[2] > s[0] + s[1])
                )
        );
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题 D: 平均

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$10$ 分

---

【问题描述】

  有一个长度为 $n$ 的数组（$n$ 是 $10$ 的倍数），每个数 $a_i$ 都是区间 $[0,9]$ 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 $i$ 个数的代价为 $b_i$，他想更改若干个数的值使得这 $10$ 种数出现的次数相等（都等于 $\frac{n}{10}$ ），请问代价和最少为多少。

【输入格式】

  输入的第一行包含一个正整数 $n$。
  接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，用一个空格分隔。

【输出格式】

  输出一行包含一个正整数表示答案。

【样例输入】

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10

【样例输出】

27

【样例说明】

  只更改第 $1,2,4,5,7,8$ 个数，需要花费代价 $1+2+4+5+7+8=27$。

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$n\le 1000$；
  对于所有评测用例，$n\le 100000,0<b_i\le 2\times 10^5$。

---

贪心

---

头一次见蓝桥贪心连着出的。
若$[0,9]$间的整数$k$在原数组中出现的次数小于等于$\frac{n}{10}$，则最优解中一定不存在由$k$变为某个数字$g$的花费$kg$，因为要是答案合法，则一定存在由$x$到$k$的花费$xk$，若直接使$x$变为$g$则总花费可以减$kg$，由此我们可以归纳出最优解一定是$[0,9]$间的出现次数大于$\frac{n}{10}$的整数每个整数变化超出的个数，而这种变化方式的最优解则是每种数字取$b$最小。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    class Pair {

        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    int[] cnt = new int[10];

    void run() {
        int n = nextInt(), m = n / 10;
        long ans = 0;
        Pair[] abs = new Pair[n];
        for (int i = 0; i < n; ++i)
            abs[i] = new Pair(nextInt(), nextInt());
        Arrays.sort(abs, (a, b) -> Integer.compare(b.b, a.b));
        for (int i = 0; i < n; ++i)
            if (++cnt[abs[i].a] > m) ans += abs[i].b;
        System.out.println(ans);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题 E: 填充

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$15$ 分

---

【问题描述】

  有一个长度为 $n$ 的 $01$ 串，其中有一些位置标记为 $?$，这些位置上可以任意填充 $0$ 或者 $1$，请问如何填充这些位置使得这个 $01$ 串中出现互不重叠的 $00$ 和 $11$ 子串最多，输出子串个数。

【输入格式】

  输入一行包含一个字符串。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

1110?0

【样例输出】

2

【样例说明】

  如果在问号处填 $0$，则最多出现一个 $00$ 和一个 $11：111000$。

【评测用例规模与约定】

  对于所有评测用例，$1\le n\le 1000000$。

---

贪心

---

？怎么还是贪心
如果以01相接的地方为断点，将01串拆分开来，如1110?0拆分成111、0?0，则显然第二段中的问号应填0，于是只需考虑若干问号存在01之间的情况，如果若干问号的左侧段长为奇数，则考虑将一个问号变为左侧段对应的值，使总答案加一，然后将所有问号变为右侧段对应的值，若剩余问号为奇数则这个数字除二向下取整是雷打不动的，而多余的一个变为左侧对答案无贡献，所以直接变右，这么模拟着递推过来就行。
实现时连续的问号同时当做0、1来看待，然后找到子串后清空累计即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            String s = in.readLine();
            int ans = 0, cnt0 = 0, cnt1 = 0;
            for (int i = 0; i < s.length(); ++i) {
                switch (s.charAt(i)) {
                    case '0':
                        ++cnt0;
                        cnt1 = 0;
                        break;
                    case '1':
                        ++cnt1;
                        cnt0 = 0;
                        break;
                    default:
                        if (cnt0 > 0) ++cnt0;
                        else if (cnt1 > 0) ++cnt1;
                        else {
                            ++cnt0;
                            ++cnt1;
                        }
                }
                if (cnt0 == 2 || cnt1 == 2) {
                    cnt0 = cnt1 = 0;
                    ++ans;
                }
            }
            System.out.println(ans);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

试题 F: 棋盘

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$15$ 分

---

【问题描述】

  小蓝拥有 $n\times n$ 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 $m$ 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

【输入格式】

  输入的第一行包含两个整数 $n,m$，用一个空格分隔，表示棋盘大小与操作数。
  接下来 $m$ 行每行包含四个整数 $x_1,y_1,x_2,y_2$，相邻整数之间使用一个空格分隔，表示将在 $x_1$ 至 $x_2$ 行和 $y_1$ 至 $y_2$ 列中的棋子颜色取反。

【输出格式】

  输出 $n$ 行，每行 $n$ 个 $0$ 或 $1$ 表示该位置棋子的颜色。如果是白色则输出 $0$，否则输出 $1$。

【样例输入】

3 3
1 1 2 2
2 2 3 3
1 1 3 3

【样例输出】

001
010
100

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$nm\le 500$；
  对于所有评测用例，$1\le n,m\le 2000，1\le x_1\le x_2\le n，1\le y_1\le y_2\le m$。

---

二维差分，捞的不谈。

import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    boolean[][] board = new boolean[2002][2002];

    void run() {
        PrintWriter out = new PrintWriter(System.out);
        int n = nextInt(), m = nextInt();
        for (int i = 0; i < m; ++i) {
            int x = nextInt(), y = nextInt();
            int k = nextInt(), g = nextInt();
            board[x][y] = !board[x][y];
            board[x][g + 1] = !board[x][g + 1];
            board[k + 1][y] = !board[k + 1][y];
            board[k + 1][g + 1] = !board[k + 1][g + 1];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                board[i][j] = (board[i][j] ^ board[i - 1][j] ^ board[i][j - 1]) ^ board[i - 1][j - 1];
                out.write(board[i][j] ? '1' : '0');
            }
            out.write('\n');
        }
        out.flush();
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题 G: 子矩阵

时间限制: $5.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$20$ 分

---

【问题描述】

  给定一个 $n\times m$ （$n$ 行 $m$ 列）的矩阵。
  设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 $a\times b$ （$a$ 行 $b$ 列）的子矩阵的价值的和。
  答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

【输入格式】

  输入的第一行包含四个整数分别表示 $n,m,a,b$，相邻整数之间使用一个空格分隔。
  接下来 $n$ 行每行包含 $m$ 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 $A_{i,j}$。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

2 3 1 2
1 2 3
4 5 6

【样例输出】

58

【样例说明】

  $1\times 2+2\times 3+4\times 5+5\times 6=58$。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$1\le n,m\le 100$；
  对于 $70\%$ 的评测用例，$1\le n,m\le 500$；
  对于所有评测用例，$1\le a\le n\le 10001\le b\le m\le 10001\le A_{i,j}\le 10^9$。

---

通过单调队列，先将矩阵(i-a+1,j)(i,j)的最值求出，然后如法炮制求出(i-a+1,j-b+1)(i,j-b+1)、(i-a+1,j-b+2)(i,j-b+2)、…、(i-a+1,j)(i,j)的最值，即(i-a+1,j-b+1)(i,j)的最值。
单调队列求最值懒得讲了，关键字：单调队列、滑动窗口、区间最值，自己搜着看吧。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int[][] matrix = new int[1001][1001], max = new int[1001][1001], min = new int[1001][1001];

    void run() {
        int n = nextInt(), m = nextInt();
        int a = nextInt(), b = nextInt();
        long ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                matrix[i][j] = nextInt();
        Deque<Integer> maxq = new ArrayDeque();
        Deque<Integer> minq = new ArrayDeque();
        for (int j = 1; j <= m; ++j) {
            maxq.clear();
            minq.clear();
            for (int i = 1; i <= n; ++i) {
                while (!maxq.isEmpty() && maxq.peekFirst() <= i - a) maxq.pollFirst();
                while (!minq.isEmpty() && minq.peekFirst() <= i - a) minq.pollFirst();
                while (!maxq.isEmpty() && matrix[i][j] >= matrix[maxq.peekLast()][j]) maxq.pollLast();
                while (!minq.isEmpty() && matrix[i][j] <= matrix[minq.peekLast()][j]) minq.pollLast();
                maxq.offerLast(i);
                minq.offerLast(i);
                max[i][j] = matrix[maxq.peekFirst()][j];
                min[i][j] = matrix[minq.peekFirst()][j];
            }
        }
        for (int i = 1; i <= n; ++i) {
            maxq.clear();
            minq.clear();
            for (int j = 1; j <= m; ++j) {
                while (!maxq.isEmpty() && maxq.peekFirst() <= j - b) maxq.pollFirst();
                while (!minq.isEmpty() && minq.peekFirst() <= j - b) minq.pollFirst();
                while (!maxq.isEmpty() && max[i][j] >= max[i][maxq.peekLast()]) maxq.pollLast();
                while (!minq.isEmpty() && min[i][j] <= min[i][minq.peekLast()]) minq.pollLast();
                maxq.offerLast(j);
                minq.offerLast(j);
                if (i >= a && j >= b)
                    ans = (ans + (long) max[i][maxq.peekFirst()] * min[i][minq.peekFirst()]) % 998244353;
            }
        }
        System.out.println(ans);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题 H: 公因数匹配

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$20$ 分

---

【问题描述】

  给定 $n$ 个正整数 $A_i$，请找出两个数 $i,j$ 使得 $i<j$ 且 $A_i$ 和 $A_j$ 存在大于 $1$ 的公因数。
  如果存在多组 $i,j$，请输出 $i$ 最小的那组。如果仍然存在多组 $i,j$，请输出 $i$ 最小的所有方案中 $j$ 最小的那组。

【输入格式】

  输入的第一行包含一个整数 $n$。
  第二行包含 $n$ 个整数分别表示 $A_1{A}_2\cdots A_n$，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含两个整数分别表示题目要求的 $i,j$，用一个空格分隔。

【样例输入】

5
5 3 2 6 9

【样例输出】

2 4

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^5，1\le A_i\le 10^6$。

---

欧拉筛计算出A范围内每个整数的本质不同质因数，易知$10^6$内整数本质不同质因数不会超过十个，从后往前遍历并记录每个因数最新一次出现位置，线性时间就能跑出来。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    static int[][] pfs = new int[1000001][];

    static {
        int[] ps = new int[328498];
        pfs[1] = new int[0];
        for (int i = 2, m = 0; i <= 1000000; ++i) {
            if (pfs[i] == null) {
                pfs[i] = new int[] { i };
                ps[m++] = i;
            }
            for (int j = 0; j < m; ++j) {
                if (i * ps[j] > 1000000) break;
                if (i % ps[j] == 0) {
                    pfs[i * ps[j]] = pfs[i];
                    break;
                }
                pfs[i * ps[j]] = new int[pfs[i].length + 1];
                System.arraycopy(pfs[i], 0, pfs[i * ps[j]], 0, pfs[i].length);
                pfs[i * ps[j]][pfs[i].length] = ps[j];
            }
        }
    }

    int[] A = new int[100001], last = new int[1000000];

    void run() {
        int n = nextInt();
        int k = n, g = n;
        for (int i = 1; i <= n; ++i)
            A[i] = nextInt();
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < pfs[A[i]].length; ++j) {
                if (last[pfs[A[i]][j]] != 0) {
                    if (k != i) {
                        k = i;
                        g = last[pfs[A[i]][j]];
                    }
                    if (last[pfs[A[i]][j]] < g) {
                        g = last[pfs[A[i]][j]];
                    }
                }
                last[pfs[A[i]][j]] = i;
            }
        }
        System.out.println(k + " " + g);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题  I: 异或和之差

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$25$ 分

---

【问题描述】

  给定一个含有 $n$ 个元素的数组 $A_i$，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

【输入格式】

  输入的第一行包含一个整数 $n$ 。
  第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

6
1 2 4 9 2 7

【样例输出】

14

【样例说明】

  两个子段可以分别选 $1$ 和 $4，9，2$，差值为 $15-1=14$。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$2\le n\le 2\times 10^5，0\le A_i\le 2^{20}$。

---

01字典树，里面存前缀异或和，然后查询[1,i][i,n]的最值，做个dp最后枚举答案。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int[] A = new int[200001], lmax = new int[200002], lmin = new int[200002], rmax = new int[200002], rmin = new int[200002];

    void run() {
        int n = nextInt(), ans = 0;
        for (int i = 1; i <= n; ++i)
            A[i] = nextInt();
        Trie lt = new Trie(), rt = new Trie();
        lmin[0] = rmin[n + 1] = 0x3f3f3f3f;
        for (int i = 1, s = 0; i <= n; ++i) {
            lt.insert(s);
            s ^= A[i];
            lmax[i] = Math.max(lmax[i - 1], lt.xorMax(s));
            lmin[i] = Math.min(lmin[i - 1], lt.xorMin(s));
        }
        for (int i = n, s = 0; i >= 1; --i) {
            rt.insert(s);
            s ^= A[i];
            rmax[i] = Math.max(rmax[i + 1], rt.xorMax(s));
            rmin[i] = Math.min(rmin[i + 1], rt.xorMin(s));
        }
        for (int i = 1; i < n; ++i) {
            ans = Math.max(ans, rmax[i + 1] - lmin[i]);
            ans = Math.max(ans, lmax[i] - rmin[i + 1]);
        }
        System.out.println(ans);
    }

    class Trie {

        int high = 20;

        Node root = new Node();

        void insert(int x) {
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit] == null)
                    cur.ch[bit] = new Node();
                cur = cur.ch[bit];
            }
        }

        int xorMax(int x) {
            int max = 0;
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit ^ 1] != null) {
                    cur = cur.ch[bit ^ 1];
                    max |= 1 << i;
                } else {
                    cur = cur.ch[bit];
                }
            }
            return max;
        }

        int xorMin(int x) {
            int min = 0;
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit] != null) {
                    cur = cur.ch[bit];
                } else {
                    min |= 1 << i;
                    cur = cur.ch[bit ^ 1];
                }
            }
            return min;
        }

        class Node {

            Node[] ch = new Node[2];
        }

    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}

---

试题 J: 太阳

时间限制: $3.0\mathrm{s}$ 内存限制: $512.0\mathrm{MB}$ 本题总分：$25$ 分

---

【问题描述】

  这天，小蓝在二维坐标系的点 $(X,Y)$ 上放了一个太阳，看做点光源。
  他拿来了 $n$ 条线段，将它们平行于 $x$ 轴放置在了坐标系中，第 $i$ 条线段的左端点在 $x_i,y_i$，长度为 $l_i$。线段之间不会有重合或部分重合的情况（但可能出现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于 $0$ 的部分被照亮就算）。

【输入格式】

  输入的第一行包含三个正整数 $n,X,Y$，相邻整数之间使用一个空格分隔。
  接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,l_i$，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个正整数表示答案。

【样例输入】

3 10 2000000
5 3 5
6 2 4
0 1 10

【样例输出】

2

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$n\le 1000$；
  对于所有评测用例，$1\le n\le 100000$，$0\le x_i,X\le 10^7$，$0<y_i\le 10^5$，$0<l_i\le 100$，$10^6<Y\le 10^7$。

线段按高度降序重排，然后投射到x轴上就成了区间覆盖问题，x轴上的端点将y=0代入y=kx+b可得x=-b/k

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    Fraction[] y0 = new Fraction[200000];

    int X, Y, m = -1;

    class Line {

        int w;

        Fraction x1, x2;
    }

    Fraction y0x(int x, int y) {
        if (X == x) return new Fraction(1, x);
        Fraction k = new Fraction(X - x, Y - y);
        Fraction b = new Fraction(k.numerator, k.denominator * x - k.numerator * y);
        return new Fraction(b.numerator * k.denominator, b.denominator * k.numerator);
    }

    void run() {
        int n = nextInt(), ans = 0, t = 0;
        X = nextInt();
        Y = nextInt();
        Line[] lines = new Line[n];
        for (int i = 0; i < n; ++i) {
            int x = nextInt(), y = nextInt(), l = nextInt();
            lines[i] = new Line();
            lines[i].w = y;
            y0[t++] = lines[i].x1 = y0x(x, y);
            y0[t++] = lines[i].x2 = y0x(x + l, y);
        }
        Arrays.sort(lines, (a, b) -> Integer.compare(b.w, a.w));
        Arrays.sort(y0, 0, t);
        for (int i = 0; i < t; ++i)
            if (m == -1 || !y0[i].equals(y0[m]))
                y0[++m] = y0[i];
        for (int i = 0; i < n; ++i) {
            int l = Arrays.binarySearch(y0, 0, m + 1, lines[i].x1);
            int r = Arrays.binarySearch(y0, 0, m + 1, lines[i].x2);
            if (!query(l, r - 1)) ++ans;
        }
        System.out.println(ans);
    }

    class Fraction implements Comparable<Fraction> {

        long numerator, denominator;

        Fraction(long numerator, long denominator) {
            this.denominator = denominator;
            this.numerator = numerator;
            this.simple();
        }

        void simple() {
            long gcd = gcd(numerator, denominator);
            this.denominator = denominator /gcd;
            this.numerator = numerator / gcd;
        }

        long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

        public boolean equals(Object obj) {
            Fraction fobj = (Fraction) obj;
            return this.numerator == fobj.numerator && this.denominator == fobj.denominator;
        }

        public int compareTo(Fraction o) {
            if (this.equals(o)) return 0;
            return Double.compare((double) this.denominator / this.numerator, (double) o.denominator / o.numerator);
        }

        @Override
        public String toString() {
            return Double.toString((double) this.denominator / this.numerator);
        }
    }

    boolean[] tree = new boolean[1 << 19];

    boolean query(int l, int r) { return queryAndUpdate(1, 0, m, l ,r); }

    boolean queryAndUpdate(int n, int L, int R, int l, int r) {
        if (tree[n]) return true;
        if (l <= L && r >= R) {
            tree[n] = true;
            return false;
        }
        int mid = (L + R) >> 1;
        boolean full = true;
        if (l <= mid) full &= queryAndUpdate(n << 1, L, mid, l, r);
        if (r > mid) full &= queryAndUpdate((n << 1) | 1, mid + 1, R, l, r);
        tree[n] = tree[n << 1] & tree[(n << 1) | 1];
        return full;
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}