这个题没做出来就离谱，下午做完LCCUP脑子就不转了，和上周的情况一模一样

T3 4412. 构造数组

image.png

思路：
模拟，更新最右值

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static final int N = 200010, MOD = 998244353;
  6.     static Map<Integer, Integer> left = new HashMap<>();
  7.     static Map<Integer, Integer> right = new HashMap<>();
  8.     static int n;
  9.     static int[] a = new int[N];
  10.     public static void main(String[] sss) throws IOException{
  11.         // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  12.         // BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  13.         Scanner sc = new Scanner(System.in);
  14.         n = sc.nextInt();
  15.         for (int i = 0; i < n; i++)
  16.             a[i] = sc.nextInt();
  19.         for (int i = 0; i < n; i++) {
  20.             if (left.get(a[i]) == null)
  21.                 left.put(a[i], i);
  22.         }
  23.         for (int i = n - 1; i >= 0; i--) {
  24.             if (right.get(a[i]) == null)
  25.                 right.put(a[i], i);
  26.         }
  28.         long res = 1;
  29.         int i = 0;
  30.         while (i < n) {
  31.             int x = left.get(a[i]), y = right.get(a[i]);
  32.             if (x == i) {
  33.                 if (i != 0)
  34.                     res = (2 * res) % MOD;
  35.             }
  36.             int ne = y + 1;
  37.             for (int j = i; j < ne; j++)
  38.                 ne = Math.max(ne, right.get(a[j]) + 1);
  39.             i = ne;
  40.         }
  41.         System.out.println(res);
  43.         // bw.close();
  44.         // br.close();
  45.     }
  46. }

类似的题：
763. 划分字母区间