Codeforces Round 852 (Div. 2) - D. Moscow Gorillas (1800)

D. Moscow Gorillas

계속 두 배열에서 어떤 $i$값에 대해서 구간을 관리한다. $k$가 나오는 구간이 $a$에선 $i$이고 $b$에선 $j$라면 $\text{Min}(i, j) \sim \text{Max}(i, j)$ 처럼 생각한다. 이 구간을 $L_i, R_i$ 라고 하자.

MEX값이 $1$부터 $n+1$가 나오는 경우까지 따져보자.

MEX값이 $1$인 곳은 $1$이 아예 안나오는 구간들이므로 $L_1$ 왼쪽 전체랑 $R_1$ 오른쪽 전체에서 이것이 나온다.

이제 MEX가 2인곳은 $1$이 둘다 포함되며 $2$가 하나도 포함되지 않는 구간이다.

이제 $L_2$와 $R_2$를 본다. 이것이 모두 현재 관리하고 있는 구간 밖에 있다면 해당 케이스만큼 조합적으로 더해줄 수 있다.

구간 안에있다면 더해줄 것은 없다.

그리고 구간을또 $L_2, R_2$를 이용해 왼쪽 오른쪽으로 더 갈수있다면 확장한다.

이렇게 MEX=$n+1$ 인 경우까지 모두 세주면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n), b(n);
   fv(a);
   fv(b);
   for (int &i: a) i--;
   for (int &i: b) i--;
   vi aidx(n), bidx(n);
   for (int i = 0; i < n; i++) aidx[a[i]] = i, bidx[b[i]] = i;
   int l = 1e9, r = -1e9;
 
   int ans = 0;
   // compute MEX = 0
   mina(l, aidx[0]);
   mina(l, bidx[0]);
   maxa(r, aidx[0]);
   maxa(r, bidx[0]);
 
   if (l > 0) {
      int len = l;
      ans += len * (len + 1) / 2;
   }
   if (r < n - 1) {
      int len = n - 1 - r;
      ans += len * (len + 1) / 2;
   }
   if (l + 1 < r) {
      int len = r - l - 1;
      ans += len * (len + 1) / 2;
   }
 
   // compute MEX = i
   for (int i = 1; i < n; i++) {
      int i1 = aidx[i];
      int i2 = bidx[i];
 
      if (i1 > i2) swap(i1, i2);
      if (i1 >= l && i1 <= r || i2 >= l && i2 <= r) {
         
      } else if (i2 < l) {
         int left_len = l - i2;
         int right_len = n - r;
         ans += left_len * right_len;
      } else if (i1 > r) {
         int left_len = l + 1;
         int right_len = i1 - r;
         ans += left_len * right_len;
      } else {
         int left_len = l - i1;
         int right_len = i2 - r;
         ans += left_len * right_len;
      }
 
      mina(l, min(i1, i2));
      maxa(r, max(i1, i2));
   }
   cout << ans + 1;
}