二分答案汇总

小团的默契游戏

小团从某不知名论坛上突然得到了一个测试默契度的游戏，想和小美玩一次来检验两人的默契程度。游戏规则十分简单，首先给出一个长度为 n 的序列，最大值不超过 m 。
小团和小美各自选择一个 [1,m] 之间的整数，设小美选择的是 l ，小团选择的是 r ，我们认为两个人是默契的需要满足以下条件:

l 小于等于 r 。
对于序列中的元素 x ，如果 0小团为了表现出与小美最大的默契，因此事先做了功课，他想知道能够使得两人默契的二元组 一共有多少种。
我们称一个序列 A 为单调不下降的，当且仅当对于任意的 i>j ，满足 A[i]>=A[j] 。

输入：
- 输入第一行包含两个正整数 m 和 n ，表示序列元素的最大值和序列的长度。
- 输入第二行包含 n 个正整数，表示该序列。
输出：
- 输出仅包含一个整数，表示能使得两人默契的二元组数量。
示例：

输入：
5 5
4 1 4 1 2
输出：10
提示：
1 <= n, m <= 100000
请注意，本题需要自行编写「标准输入」和「标准输出」逻辑，以及自行 import/include 需要的 library。

思路：
枚举左值，二分查找右值的最小值。
问题是时间复杂度会不会过高？？？

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = br.readLine().split(" ");
        int m = Integer.parseInt(ss[0]), n = Integer.parseInt(ss[1]);
        int[] a = new int[n];
        ss = br.readLine().split(" ");
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(ss[i]);
        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            int l = i, r = m + 1;
            while (l < r) {
                int mid = l + r >> 1;
                int cur = -1;
                boolean flag = true;
                for (int j = 0; j < n; j++) {
                    if (a[j] >= i && a[j] <= mid) continue;
                    if (a[j] < cur) {
                        flag = false;
                        break;
                    } else cur = a[j];
                }
                if (flag) r = mid;
                else l = mid + 1;
            }
            if (l == m + 1) break;
            cnt += m - l + 1;
        }
        System.out.println(cnt);
        br.close();
    }
}