百度笔试 - 1015

最大的乘积

题面

给定四个正整数 $a,b,c,d$，你可以进行至多 $k$ 次操作，每次操作可以从 $a,b,c,d$ 中选择一个数，然后令这个数加 $1$，求操作后这四个正整数的乘积 $a*b*c*d$ 的最大值。

输入描述：
输入包含多组测试数据。
输入第一行包含一个正整数 $T(1≤T≤100)$，表示测试数据组数。
接下来 $T$ 行，每行描述一组测试数据，包含 $a,b,c,d,k(1≤a,b,c,d,k≤20)$ 五个整数。

输出描述：
输出包含 $T$ 行。
对于每组测试数据输出一行一个整数，表示操作后这四个正整数的乘积 $a*b*c*d$ 的最大值。

思路与代码：

数据量小，直接模拟。

先排序，每次操作将最小的数 $+1$，再重新排序进行下一次操作即可。

前缀染色

题面

李华有一块很长的画布，上面有 $n$ 个位置，位置从左至右编号为 $1$ 到 $n$，有 $m+1$ 种颜色，颜色编号为 $0$ 到 $m$，初始时画布上所有位置均为 $0$ 号颜色。

现在李华要对这块画布进行 $m$ 次染色，第 $i(1≤i≤m)$ 次染色将会把编号不大于 $x_i$ 的位置染成 $i$ 号颜色，若某些位置被多次染色，则编号较大的颜色能完全覆盖编号较小的颜色。求出李华每完成一次染色后画布上的颜色种类数（包括 $0$ 号颜色）。

输入描述：
输入第一行包含两个正整数 $n(1≤n≤10^9)$ 和 $m(1≤m≤10^5)$。
输入第二行包含 $m$ 个正整数，第 $i$ 个整数是 $xi(1≤xi≤n)$。

输出描述：
输出包含一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 次染色结束后画布上的颜色种类数。

示例：

输入：10 5
      5 3 2 4 7
输出：2 3 4 3 2

思路与代码：

线段树，只能过 $36\%$，不知道哪错了。

import java.util.*;
import java.io.*;

public class Main {
    static class SegmentTree {
        int[] lazy;
        int[] tree;
        int n;

        SegmentTree(int n) {
            this.n = n;
            int size = 4 * n;
            lazy = new int[size];
            tree = new int[size];
        }

        void update(int node, int start, int end, int l, int r, int color) {
            if (lazy[node] != 0) {
                tree[node] = lazy[node];
                if (start != end) {
                    lazy[node * 2] = lazy[node];
                    lazy[node * 2 + 1] = lazy[node];
                }
                lazy[node] = 0;
            }

            if (start > r || end < l) return;

            if (l <= start && end <= r) {
                tree[node] = color;
                if (start != end) {
                    lazy[node * 2] = color;
                    lazy[node * 2 + 1] = color;
                }
                return;
            }

            int mid = (start + end) / 2;
            update(node * 2, start, mid, l, r, color);
            update(node * 2 + 1, mid + 1, end, l, r, color);

            tree[node] = tree[node * 2] != 0 ? tree[node * 2] : tree[node * 2 + 1];
        }

        void query(int node, int start, int end, Set<Integer> colors) {
            if (lazy[node] != 0) {
                tree[node] = lazy[node];
                if (start != end) {
                    lazy[node * 2] = lazy[node];
                    lazy[node * 2 + 1] = lazy[node];
                }
                lazy[node] = 0;
            }

            if (start == end) {
                colors.add(tree[node]);
                return;
            }

            int mid = (start + end) / 2;
            query(node * 2, start, mid, colors);
            query(node * 2 + 1, mid + 1, end, colors);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        String[] xStr = br.readLine().split(" ");
        int[] x = new int[m];
        for (int i = 0; i < m; i++) {
            x[i] = Integer.parseInt(xStr[i]);
        }

        SegmentTree st = new SegmentTree(n);
        StringBuilder sb = new StringBuilder();
        Set<Integer> colors = new HashSet<>();

        for (int i = 0; i < m; i++) {
            st.update(1, 1, n, 1, x[i], i + 1);
            colors.clear();
            st.query(1, 1, n, colors);
            sb.append(colors.size()).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}