package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_787归并排序 {
    static Scanner in = new Scanner(System.in);

    static int N = 100010;
    static int n;
    static int[] a = new int[N];
    static int[] t = new int[N];

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();
        mergeSort(0, n - 1);
        for (int i = 0; i < n; i ++) System.out.print(a[i] + " ");
    }

    public static void mergeSort(int l, int r) {
        if (l >= r) return ;
        int mid = l + r >> 1;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) t[k ++] = a[i] <= a[j] ? a[i ++] : a[j ++];
        while (i <= mid) t[k ++] = a[i ++];
        while (j <= r) t[k ++] = a[j ++];
        for (k = 0, i = l; i <= r; k ++, i ++) a[i] = t[k];
    }
}

package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_466回文日期 {
    /**
     *  枚举
     *  如果前4位已经确定，那么后4位也确定了，所以枚举前4位。
     *  思路：1、枚举前4位回文数。
     *       2、判断日期是否在规定范围内。
     *       3、判断日期是否合法。
     */
    static Scanner in = new Scanner(System.in);

    static int date1, date2;
    static int[] days = new int[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // 检查当前时间是否合法
    public static boolean check(int date) {
        int y = date / 10000;           // 年
        int m = date % 10000 / 100;     // 月
        int d = date % 100;             // 日

        if (m < 1 || m > 12) return false;
        if (m != 2) {                   // 不是2月
            return d <= days[m];
        } else {                        // 是2月
            // 四年一闰，百年不闰，四百年又一闰。
            boolean flag = ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
            if (flag) return d <= days[m] + 1;
            else return d <= days[m];
        }
    }

    public static void main(String[] args) {
        date1 = in.nextInt();
        date2 = in.nextInt();

        int ans = 0;
        for (int i = 1000; i < 10000; i ++) {
            int x = i;
            int date = i;
            for (int j = 0; j < 4; j ++) {
                date = date * 10 + (x % 10);
                x /= 10;
            }

            if (date1 <= date && date <= date2 && check(date)) ans ++;
        }
        System.out.println(ans);
    }
}

package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1204错误票据 {
    static Scanner in = new Scanner(System.in);

    static int N = 100010;
    static int n;
    static int[] cnt = new int[N];

    public static void main(String[] args) {
        // min记录开始值，max记录结束值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int n = in.nextInt();
        while (in.hasNextInt()) {
            int t = in.nextInt();
            cnt[t] ++;
            min = Math.min(min, t);
            max = Math.max(max, t);
        }

        int ans1 = 0, ans2 = 0;
        for (int i = min; i <= max; i ++) {
            if (cnt[i] == 0) ans1 = i;
            if (cnt[i] == 2) ans2 = i;
        }
        System.out.println(ans1 + " " + ans2);
    }
}

package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1245特别数的和 {
    // 模拟，如果数位中有2019就加上
    static Scanner in = new Scanner(System.in);

    static int n;

    public static void main(String[] args) {
        n = in.nextInt();
        long ans = 0;
        for (int i = 1; i <= n; i ++) {
            int x = i;
            while (x != 0) {
                int t = x % 10;
                x /= 10;
                if (t == 2 || t == 0 || t == 1 || t == 9) {
                    ans += i;
                    break;
                }
            }
        }
        System.out.println(ans);
    }
}

package 第4讲枚举模拟与排序;

import java.util.Arrays;
import java.util.Scanner;

public class 例题_1236递增三元组 {
    /**
     *  数据范围在10^5，时间复杂度在O(nlogn)以内，所以最多只能枚举1个数组。
     *  而AC两个数组在两端，枚举A时，只能限制B，但不能限制C，所以我们枚举B数组。
     * 
     *  主要思想：枚举B数组，再分别求出A数组中小于当前Bi和C数组中大于当前Bi的个数，相乘累加即是答案。
     *  求个数有两种方法：1、前缀和
     *                  2、二分
     *  （这里用二分吧，简单一些，hh，注意边界问题0或者n-1时个数可能不存在）
     */
    static Scanner in = new Scanner(System.in);

    static int N = 10010;
    static int n;

    public static void main(String[] args) {
        int n = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();       
        for (int i = 0; i < n; i ++) b[i] = in.nextInt();       
        for (int i = 0; i < n; i ++) c[i] = in.nextInt();       
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);

        long ans = 0;
        for (int i = 0; i < n; i ++) {
            // 二分A数组中比Bi小的个数
            int al = 0;
            int ar = n - 1;
            while (al < ar) {
                int mid = al + ar + 1 >> 1;
                if (a[mid] < b[i]) al = mid;
                else ar = mid - 1;
            }
            long cnta;
            if (al == 0 && a[al] >= b[i]) cnta = 0; // 个数不存
            else cnta = (al - 0) + 1;

            // 二分C数组中比Bi大的数
            int cl = 0;
            int cr = n - 1;
            while (cl < cr) {
                int mid = cl + cr >> 1;
                if (c[mid] > b[i]) cr = mid;
                else cl = mid + 1;
            }
            long cntc;
            if (cl == n - 1 && c[cl] <= b[i]) cntc = 0; //个数不存在
            else cntc = ((n - 1) - cl) + 1;

            ans += cnta * cntc;
        }
        System.out.println(ans);
    }
}

package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1210连号区间数 {
    /** 
     *  注意给出的数据就包含1~n的所有数，并且每个数字只出现一次。
     *  两重循环，第一重循环固定左端点，第二重循环固定右端点
     *  思路：在区间l~r中找到最大值max和最小值min，如果max - min == r - l，
     *                                      说明当前区间是递增且连续的
     *  例如：一个区间[4,6,7,5] max = 7, min = 4, 7 - 4 == 3 - 0, 所以是连续的
     *       一个区间[5,3,2,6] max = 6, min = 2, 6 - 2 != 3 - 0, 所以不是连续的
     */
    static Scanner in = new Scanner(System.in);

    static int N = 10010;
    static int n;
    static int[] a = new int[N];

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();

        int ans = 0;
        for (int i = 0; i < n; i ++) {
            // 由于区间不断一直变大，max和min只会不断变大和变小
            // 所以不需要对每一个新区间都遍历一次
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int j = i; j < n; j ++) {
                min = Math.min(min, a[j]);
                max = Math.max(max, a[j]);
                if (max - min == j - i) ans ++;
            }
        }
        System.out.println(ans);
    }
}

package acwing.race;

import java.util.Arrays;
import java.util.Scanner;

public class 最大中位数3578 {
    /**
     *  这居然是一个二分！！！
     *  二分最大中位数答案，再将中位数右边的数补齐至当前中位数，判断操作次数是否小于k。
     */
    static Scanner in = new Scanner(System.in);

    static int n, k;

    public static void main(String[] args) {
        n = in.nextInt();
        k = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();
        Arrays.sort(a);

        long l = 0, r = Integer.MAX_VALUE;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (check(a, mid)) l = mid;
            else r = mid - 1;
        }
        System.out.println(l);
    }

    // 检查当前中位数为x时，操作次数是否足够
    public static boolean check(int[] a, long x) {
        long sum = 0;
        for (int i = n / 2; i < n; i ++) {
            if (x > a[i]) sum += x - a[i];
        }
        return sum <= k;
    }
}

package acwing.race;

import java.util.Scanner;

public class 数字移动3579 {
    /**
     *  这题首要任务就是把题目看懂!!!
     *  把题目看懂了，分析题目就明白是用并查集求连通块大小
     */
    static Scanner in = new Scanner(System.in);

    static int N = 200010;
    static int[] p = new int[N];
    static int[] s = new int[N];

    public static void main(String[] args) {
        int t = in.nextInt();
        while (t -- > 0) {
            int n = in.nextInt();
            for (int i = 1; i <= n; i ++) {
                p[i] = i;
                s[i] = 1;
            }
            for (int i = 1; i <= n; i ++) {
                int j = in.nextInt();
                if (find(i) != find(j)) {
                    s[find(i)] += s[find(j)];
                    p[find(j)] = find(i);
                }
            }

            for (int i = 1; i <= n; i ++) System.out.print(s[find(i)] + " ");
            System.out.println();
        }
    }

    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

package acwing.lanqiaobei;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 最长非递减子序列3549 {
    /**
     *  y总思想题解，新数字序列a的最长非递减子序列，翻转之前状态肯定是
     *      有4段：111...222...111...222，其中中间的两段是需要翻转，且每段长度允许为0。
     * 
     *  这个是y总的简单化代码，非常简洁。
     */
    static In in = new In(System.in);

    public static void main(String[] args) throws Exception {
        int n = in.nextInt();

        // 注意：s1是前1段最大长度，s2是前2段的最大长度，以此类推！！
        int s1 = 0, s2 = 0, s3 = 0, s4 = 0; 
        while (n -- > 0) {
            int x = in.nextInt();
            if (x == 1) {                   
                s1 = s1 + 1;                    // 直接加在第1段后面。
                s3 = Math.max(s2 + 1, s3 + 1);  // 接在第2段后面或者在第3段后面加。
            } else {
                s2 = Math.max(s1 + 1, s2 + 1);  // 接在第1段后面或者在第2段后面加。
                s4 = Math.max(s3 + 1, s4 + 1);  // 接在第3段后面或者在第3段后面加。
            }
        }

        // 输出最长的一段，1中s3最长，2中s4最长
        System.out.println(Math.max(s3, s4));
    }
}

class In{
    BufferedReader reader;
    StringTokenizer tokenizer;

    In(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() throws Exception {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }
}

package acwing.lanqiaobei;

import java.util.Scanner;

public class 双端队列3548 {
    /**
     *  注意数据范围在2×10^5，而且队列中一定不会存在重复数字
     *  
     *  直接用一个数组记录数字所在的下标，每次查询输出距离左右端点的最小值即可。
     *      y总的方法甚至不需要保存数据，只保存下标。
     */
    static Scanner in = new Scanner(System.in);

    static int N = 200010;
    static int q, x;
    static int[] a = new int[N];    // 模拟队列（该数组可以直接删除）
    static int[] sign = new int[N]; // 纪录下标

    public static void main(String[] args) {
        q = in.nextInt();
        int l = N / 2, r = N / 2 + 1;
        while (q -- > 0) {
            String s = in.next();
            x = in.nextInt();
            if (s.equals("L")) {
                a[l] = x;
                sign[x] = l;
                l --;
            } else if (s.equals("R")) {
                a[r] = x;
                sign[x] = r;
                r ++;
            } else {
                int ans = Math.min(sign[x] - (l + 1), (r - 1) - sign[x]);
                System.out.println(ans);
            }
        }
    }
}