D. Moscow Gorillas

계속 두 배열에서 어떤 ii값에 대해서 구간을 관리한다. kk가 나오는 구간이 aa에선 ii이고 bb에선 jj라면 Min(i,j)∼Max(i,j)\text{Min}(i, j) \sim \text{Max}(i, j) 처럼 생각한다. 이 구간을 Li,RiL_i, R_i 라고 하자.

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

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

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

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

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

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

이렇게 MEX=n+1n+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;
}

Comments

You may also enjoy