[Codeforces Round 1005(Div. 2)] - D. Eating

https://codeforces.com/contest/2064/problem/D

Codeforces Round 1005(Div. 2) - D. Eating

문제 유형: 그리디, 비트마스킹, 이진 탐색

시간 제한: 5초

메모리 제한: 512MB

 

문제

There are n slimes on a line, the i-th of which has weight wi. Slime i is able to eat another slime j if wi≥wj; afterwards, slime j disappears and the weight of slime i becomes wi⊕wj.

The King of Slimes wants to run an experiment with parameter x as follows:

• Add a new slime with weight x to the right end of the line (after the n-th slime).

• This new slime eats the slime to its left if it is able to, and then takes its place (moves one place to the left). It will continue to do this until there is either no slime to its left or the weight of the slime to its left is greater than its own weight. (No other slimes are eaten during this process.)
• The score of this experiment is the total number of slimes eaten.

The King of Slimes is going to ask you q queries. In each query, you will be given an integer x, and you need to determine the score of the experiment with parameter x.

Note that the King does not want you to actually perform each experiment; his slimes would die, which is not ideal. He is only asking what the hypothetical score is; in other words, the queries are not persistent.

 

n마리의 슬라임이 줄을서고 있습니다. 슬라임 i는 무게 wi가 있는데, 만약 두 슬라임 i, j에서 wi >= wj면, i는 j를 먹고, wi는 wi⊕wj가 됩니다.

 

슬라임들의 왕은 실험을 하고 싶어합니다:

• 슬라임들의 줄의 오른쪽 맨 뒤에 슬라임을 추가합니다.
• 새로운 슬라임이 왼쪽에 먹을 수 있는 슬라임이 있다면, 먹습니다.
• 이를 왼쪽 슬라임이 못 먹는 슬라임이거나 모든 슬라임을 먹을 때까지 반복합니다.
• 점수는 새로운 슬라임이 기존 슬라임을 먹은 횟수입니다.

왕은 q개의 질의를 합니다.

각 쿼리에 정수 x를 받는데, 그 x만한 크기의 새로운 슬라임으로 실험한다고 가정하고 점수를 구해야 합니다.

각 쿼리는 독립적입니다.

 

입력

The first line contains an integer t (1≤t≤10^4) — the number of test cases.

The first line of each test case contains integers n and q (1≤n,q≤2⋅10^5) — the number of slimes and the number of queries, respectively.

The following line contains n integers w1,w2,…,wn (1≤wi<2^30) — the weights of the slimes.

The following q lines contain a single integer x (1≤x<2^30) — the parameter for the experiment.

The sum of n does not exceed 2⋅10^5 and the sum of q does not exceed 2⋅105 across all test cases.

 

첫째 줄에 테스트 케이스의 개수 t가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 n과 q가 주어집니다. n은 슬라임의 개수, q는 질의의 개수입니다.

다음 줄에는 n개의 정수 w1, w2, ..., wn이 주어집니다. 각 슬라임들의 무게입니다.

다음 q개의 줄에는 x가 주어집니다. 실험의 파라미터입니다.

 

출력

For each query, output a single integer — the score of the experiment.

각 쿼리마다의 실험 점수를 출력하시오.

 

풀이

Editorial: https://codeforces.com/blog/entry/138912

나이브하게 쿼리를 시뮬레이션하는 것은 TLE에 걸린다.

대신, 우리는 MSB가 더 큰 경우, 반드시 그 슬라임을 먹을 수 있다는 것을 알 수 있다.

MSB가 같으면, 상세한 비교가 필요하긴 하다.

 

last[idx][msb] = 현재 idx이하의 현재 msb와 똑같은 가장 오른쪽의 인덱스를 저장한다고 하자.

우리는 이 2D배열을 프리컴퓨트 할 수 있다.

 

이제, 시뮬레이션을 시작한다.

idx = n-1부터 시작한다. idx는 새 슬라임이 상대할 슬라임의 위치를 말한다.

우선, 현재 x의 msb를 구하고, last[idx][msb]를 통해서 가장 오른쪽의 같은 msb를 가진 인덱스로 건너뛴다.

그러고, x는 nxt ~ idx까지의 구간 xor을 해주면 된다. 이는 구간 xor을 미리 계산해둔 값을 이용하면 된다.

pre[i]를 [0, i]범위의 x이라고 하고, x ^= pre[nxt] ^ pre[idx]를 계산하면, idx부터 nxt+1까지 슬라임을 먹고 크기 변화에 반영이 되었다는 의미이다. 그 뒤, idx를 nxt로 업데이트 해준다.

 

만약 nxt가 -1이거나, nxt의 무게가 x보다 크다면, 슬라임이 최대로 왔다는 의미로, 종료 후 n - idx -1을 출력해서 점수를 표시한다.

그게 아니라면, idx를 1 줄이고 nxt의 크기만큼 xor해서 해당 슬라임을 먹은 것으로 간주해주면 된다. 이를 종료 조건 이전까지 계속 반복한다.

 

 

코드

C++

#include <bits/stdc++.h>
#define LIMIT 2 * (int)1e5
using namespace std;

const int W = 30;

void solve() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n), pre(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (i == 0) {
      pre[i] = a[i];
    } else {
      pre[i] = pre[i - 1] ^ a[i];
    }
  }

  vector<vector<int>> last(n, vector<int>(W));
  for (int i = 0; i < n; ++i) {
    if (i > 0) {
      last[i] = last[i - 1];
    }
    last[i][(int)log2(a[i])] = i;

    for (int j = W - 2; j >= 0; --j) {
      last[i][j] = max(last[i][j], last[i][j + 1]);
    }
  }

  while (q--) {
    int x;
    cin >> x;

    int idx = n - 1;
    while (idx >= 0 && x > 0) {
      int msb = (int)log2(x);
      int nxt = last[idx][msb];

      x ^= pre[idx] ^ pre[nxt];
      idx = nxt;

      if (nxt == -1 || a[nxt] > x)
        break;

      x ^= a[nxt];
      idx--;
    }

    cout << n - idx - 1 << " ";
  }

  cout << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}