BOJ 27933 - 대회 이름 정하기

BOJ 27933 - 대회 이름 정하기

열심히 구간합 배열을 만들자.

모든 $Y$와 $K$에 대해 양옆으로 같은것들을 그룹으로 보고 각 위치가 어떤 그룹에 속하는지 보자.

$[L, R]$ 쿼리에서 $L$의 그룹을 $G_L$ 이라 할 때, $G_{L+1} \sim G_{R-1}$ 의 모든 그룹들은 항상 그룹에서 최대값을 고를 수 있다.

이제 $L$과 $R$이 속한 그룹이 $Y$냐 $K$냐에 따라서, 적절히 그룹에서 현재 인덱스를 포함한 왼쪽이나 오른쪽의 최대값을 이용해 연산해줄수 있다.

void solve() {  
   int n, q;  
   string s;  
   cin >> n >> s;  
   vi a(n);  
   fv(a);  
   vi idx(n);  
  
   for (int i = 0, j = 0; i < n; i++) {  
      if (!i || s[i] != s[i - 1]) {  
         idx[i] = j++;  
      } else {  
         idx[i] = idx[i - 1];  
      }  
   }  
   vi mx_l(n), mx_r(n);  
   for (int i = 0; i < n; i++) {  
      if (i && idx[i] == idx[i - 1]) mx_l[i] = max(mx_l[i - 1], a[i]);  
      else mx_l[i] = a[i];  
   }  
   for (int i = n - 1; i >= 0; i--) {  
      if (i < n - 1 && idx[i] == idx[i + 1]) mx_r[i] = max(mx_r[i + 1], a[i]);  
      else mx_r[i] = a[i];  
   }  
   int G = idx[n - 1] + 1;  
   vi maxs(G);  
   for (int i = 0; i < n; i++) maxs[idx[i]] = max(mx_l[i], mx_r[i]);  
   vi psum(G + 1);  
   for (int i = 0; i < G; i++) psum[i + 1] = psum[i] + maxs[i];  
   auto query = [&](int l, int r) {  
      if (l > r)return 0LL;  
      return psum[r + 1] - psum[l];  
   };  
  
   cin >> q;  
   while (q--) {  
      int l, r;  
      cin >> l >> r, l--, r--;  
      int yk = 0, ky = 0;  
      int lg_idx = idx[l];  
      int rg_idx = idx[r];  
      if (lg_idx == rg_idx) {  
  
      } else {  
         { // YK  
            yk = query(lg_idx + 1, rg_idx - 1);  
            if (s[l] == 'Y') yk += mx_r[l];  
            if (s[r] == 'K') yk += mx_l[r];  
         }  
         {  
            ky = query(lg_idx + 1, rg_idx - 1);  
            if (s[l] == 'K') ky += mx_r[l];  
            if (s[r] == 'Y') ky += mx_l[r];  
         }  
      }  
      if (yk > ky) {  
         cout << "Y " << yk << endl;  
      } else if (yk < ky) {  
         cout << "K " << ky << endl;  
      } else {  
         cout << "YK " << ky << endl;  
      }  
   }  
}