E. Distance Learning Courses in MAC:
题目大意:
思路解析:
// 对于这种二进制多个数计算答案,我们应该灵敏的想到是否可以通过枚举二进制位来计算答案。
就是对每一个查询找出或和的最大值,那我们想xi 和 yi中哪些位一定会出现在答案中,假设为25 和 31,他们两转为二进制为 (11001) 和 (11111)我们可以想到24一定会进入答案,如果它不是答案的一部分,那无论怎么选都无法满足选择的数大于等于x。那我们这样就可以对[l,r]的答案进行简单计算(这里利用线段树或者树状数组的区间查询即可),那后续剩下的答案怎么办。后续 x 和 y剩下的二进制位为 (00001) 和 (0111)我们发现对r的剩余无论选择哪一位都可以满足大于等于x,那我们可以对于这些剩下的数做一个前缀和的处理,如果有我们一定会把它假如答案。
那么如果假如剩下 有00100这一位,之前粗略的答案中也有00100这一位可以发现我们可以将其转化为00111,后面就可以不用枚举了。
代码实现:
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int inf = (int) 1e9;
static int mod = 998244353;
public static void main(String[] args) throws IOException {
int t = f.nextInt();
while (t > 0) {
solve();
t--;
}
w.flush();
w.close();
br.close();
}
static int n;
static int[] l;
static int[] r;
static int[] v;
static int maxN = (int) 2e5 + 5;
static int[] t = new int[maxN * 2];
public static void solve() {
n = f.nextInt();
l = new int[n + 1];
r = new int[n + 1];
v = new int[n + 1];
for (int i = 1; i <= n; i++) {
l[i] = f.nextInt();
r[i] = f.nextInt();
}
fix();
int[][] bits = new int[31][n + 1];
for (int i = 1; i <= n; i++) {
update(i, v[i]);
for (int j = 30; j >= 0; j--) {
bits[j][i] = bits[j][i-1];
if (((r[i] >> j) & 1) == 1) bits[j][i]++;
}
}
int q = f.nextInt();
for (int i = 0; i < q; i++) {
int x = f.nextInt();
int y = f.nextInt();
int ans = sum(x, y);
for (int j = 30; j >= 0; j--) {
int cnt = bits[j][y] - bits[j][x-1] + ((ans >> j) & 1);
if (cnt > 1) {
ans |= (2 << j) - 1;
break;
} else if (cnt == 1) {
ans |= (1 << j);
}
}
w.print(ans + " ");
}
w.println();
for (int i = 0; i <= n; i++) {
t[i] = 0;
}
}
// public static void fix(){
// for (int i = 1; i <= n; i++) {
// if (l[i] == r[i]){
// v[i] = r[i];
// l[i] = r[i] = 0;
// continue;
// }
// int pref = (1 << (lg(l[i] ^ r[i]) + 1)) - 1;
// v[i] = r[i] - (r[i] & pref);
// r[i] = r[i] & pref;
// l[i] = l[i] & pref;
// }
// }
public static void fix() {
for (int i = 1; i <= n; ++i) {
if (l[i] == r[i]) {
v[i] = l[i];
l[i] = r[i] = 0;
continue;
}
int pref = (1 << (lg(l[i] ^ r[i]) + 1)) - 1;
v[i] = r[i] - (r[i] & pref);
r[i] &= pref;
l[i] &= pref;
}
}
public static void update(int x, int val) {
for (int i = x; i <= n; i += lowbit(i)) {
t[i] |= val;
}
}
public static int lg(int x) {
for (int i = 30; i >= 0; i--) {
if (((x >> i) & 1) == 1) return i;
}
return 0;
}
public static int sum(int l, int r) {
int res = 0;
while (l <= r) {
res |= v[r];
r--;
while (r - lowbit(r) >= l) {
res |= t[r];
r -= lowbit(r);
}
}
return res;
}
public static int lowbit(int x) {
return x & -x;
}
static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
static Input f = new Input(System.in);
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Input {
public BufferedReader reader;
public StringTokenizer tokenizer;
public Input(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
String str = null;
try {
str = reader.readLine();
} catch (IOException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
return str;
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
}
}