D. Find the Different Ones!

题目描述：D. Find the Different Ones!

---

解题思路

---

• 解题思路

  1、假设一开始数列中所有数都是相同的，此时是无解的，研究出现不同时的特点。此时如果有一个 $a_x$ 的值与其他元素不同，则一定有 $a_{x-1} \not= a_x$ (相邻位置元素不同)
  2、一种方法是 set 加二分：遍历序列，当出现 $a_x \not= a_{x-1}$ 时，将 $\{ x-1,x \}$ 计入 set。询问区间 $[L, R]$ 时，通过二分从 set 中查找一个大于 $L$ 的 $x$，这一组 $\{ x-1,x \}$ 便可以是答案
  3、另一种方法是前缀和加二分：用前缀和的方式处理一个 $s[]$，令 $s[i]$ 表示区间 $[1, i]$ 共有多少个 $a_{x-1} \not= a_x$，则 $s[x] - s[L]$ 便可表示区间 $[L, x]$ 的情况，只要 $s[x] - s[L] > 0$ ，则一定有满足题意的结果。简单可知，$s[]$ 一定是单调不减的(升序)，所以可以用二分的方式，找到一个大于 $s[L]$ 的 $s[x]$ ，则 $\{x-1, x\}$ 便可以是答案
  4、下面的代码实现，采用的是第二种方法

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 2e5 + 10;
  
  int a[N], s[N];
  
  void solve()
  {
      int n;
      cin >> n;
      for (int i = 1; i <= n; i++)
          cin >> a[i];
  
      // 处理 s[]
      for (int i = 2; i <= n; i++)
          s[i] = s[i - 1] + (a[i] != a[i - 1]);
  
      int q;
      cin >> q;
      while (q--)
      {
          int l, r;
          cin >> l >> r;
  
          // 二分查找一个 > s[l] 的 s[x]
          int x = upper_bound(s + l + 1, s + r + 1, s[l]) - s;
          if (x > r)
              cout << "-1 -1\n";
          else
              cout << x - 1 << ' ' << x << '\n';
      }
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---