https://codeforces.com/contest/1878/problem/E

문제 요약

• $t$: 테스트 케이스 수
• 길이 $n$인 배열 $a$에 대해 $f(l, r) = a_l \ \&\ a_{l+1}\ \&\ \dots \ \&\ a_r$이라 하자.
  • $1 \le l \le r \le n$, $\&$는 bitwise AND
• 주어진 $n$, $[a_1,\ \dots,\ a_n]$에 대해 질의로 $l$, $k$가 $q$번 주어진다.
  • 각 질의에 대해 $f(l, r) \ge k$를 만족하는 $r$의 최댓값을 찾아라.
  • 그런 $r$이 하나도 없다면 $-1$을 출력하라.
• 주요 제약사항
  • 배열 $a$의 길이: $1 \le n \le 2 \times 10^5$
  • 질의 수: $1 \le q \le 10^5$

아이디어

• 시간 복잡도에 매우 주의해야 한다.
  • $O(n^2)$, $O(nq)$보다 빨라야 한다.
• $f(l, r)$을 빠르게 구해야 하므로 주어진 배열로 세그먼트 트리를 구성한다.
  • 비어있는 자리는 $11...1_2$ 값으로 채우면 된다.
    • $11...1_2\ \&\ x = x$가 되기 때문 (항등원)
• $r$이 클 수록 $f(l, r)$은 감소하는 특징이 있다.
  • 따라서 이분 탐색으로 $r$을 빠르게 찾을 수 있다.
  • $r$은 $f(l, r) \ge k$를 만족하는 upper bound다.
• 총 시간 복잡도는 $O(n + q \times (\lg n)^2$)다.
  • 세그먼트 트리 구성: $O(n)$
  • $q$번의 질의: $O(q)$
    • $f(l, r)$ 값 구하기: $O(\lg n)$
    • upper bound $r$ 찾기: $O(\lg (n-l))$ = $O(\lg n)$

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, n, q, l, k, r, ubn;
	static int[] segtree;
	
	static int ALL_1 = 0x7fffffff;

	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(rd.readLine());
			ubn = pow2ub(n);
			
			segtree = new int[ubn*2];
			tk = new StringTokenizer(rd.readLine());
			for (int i=1; i<ubn; i++)		segtree[i] = ALL_1;
			for (int i=ubn; i<ubn+n; i++)	segtree[i] = Integer.parseInt(tk.nextToken());
			for (int i=ubn+n; i<ubn*2; i++) segtree[i] = ALL_1;
			
			for (int i=ubn*2-1; i>1; i--) {
				segtree[i/2] &= segtree[i];
			}
			
			q = Integer.parseInt(rd.readLine());
			for (int i=0; i<q; i++) {
				tk = new StringTokenizer(rd.readLine());
				l = Integer.parseInt(tk.nextToken()) - 1;
				k = Integer.parseInt(tk.nextToken());
				
				if (segtree[ubn+l] < k) {
					sb.append(-1).append(' ');
					continue;
				}
				
				int lo = l;
				int hi = n;
				int mid = -1;
				while (lo < hi) {
					mid = lo + (hi - lo) / 2;
					if (bitands(l, mid, 0, ubn, 1) >= k) {
						lo = mid + 1;
					}
					else {
						hi = mid;
					}
				}
				
				sb.append(lo).append(' ');
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
	
	static int pow2ub(int n) {
		for (int i=0; i<32; i++) {
			if (1 << i >= n) return 1 << i;
		}
		return -1;
	}
	
	static int bitands(int l, int r, int s, int e, int idx) {
		if (e - s == 1)
			return segtree[idx];
		if (l <= s && e < r)
			return segtree[idx];
		int m = (s + e) / 2;
		int ret = ALL_1;
		if (l < m)  ret &= bitands(l, r, s, m, idx*2);
		if (r >= m) ret &= bitands(l, r, m, e, idx*2+1);
		return ret;
	}
}

메모리 및 시간

• 메모리: 27052 KB
• 시간: 1418 ms

리뷰

• CodeForces는 오랜만인데, 시간복잡도가 꽤나 빡빡했다.