CF1935E Distance Learning Courses in MAC

Posted on Edited on In

CF1935E Distance Learning Courses in MAC

题目大意

给定 \(n\) 个变量 \(z_i\in[x_i,y_i]\)，你可以在范围内任意指定 \(z_i\) 的值。
\(q\) 次查询，每次查询给定区间 \([l_i,r_i]\)，求用这些变量得到的 二进制或 最大值。

思路

选择 \(z\in[x,y]\)，贡献分为两部分

  1. \([x,y]\) 的公共前缀，这一部分贡献恒定
  2. 在第一个不同的位置，\(y\) 一定为 \(1\)，\(x\) 一定为 \(0\)
  1. 若要求贡献的这一位为 \(1\)，那么可以给到一个 \(\leq y\) 的任意值。
  2. 否则，一定可以给到后面的所有位均为 \(1\)。

Solution1

查询时，先将所有恒定贡献求或
从高位开始查询所有位置，判断是否有 (2) 类贡献
若没有 (2) 类贡献，跳过
若有 2 个 (2) 类贡献，或这这一位已经为 1，则从这一位往后都直接给 1 (对应 (ii))
若只有一个，设为 \(y\)，则依次考虑当前答案中为 \(0\) 的位，能给 1 就给 1 (对应 (i))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
 
const int N = 2e5 + 10;
 
int T, n, m;
int c[N][30], z[N][30], lst[N][30];
int s[N];
 
int all(int n) { return (1 << n) - 1; }
int lg(int x) { return 31 - __builtin_clz(x); }
 
int main() {
	for(scanf("%d", &T); T--; ) {
		scanf("%d", &n);
		for(int i = 1, x, y; i <= n; ++i) {
			scanf("%d%d", &x, &y);
			int l = x & ~all(lg(x ^ y) + 1);
			for(int j = 0; j < 30; ++j) 
				c[i][j] = c[i - 1][j] + ((l >> j) & 1),
				z[i][j] = z[i - 1][j],
				lst[i][j] = lst[i - 1][j];
			y ^= l;
			if(y) {
				int t = 31 - __builtin_clz(y);
				lst[i][t] = y, z[i][t]++;
			}
		}
		scanf("%d", &m);
		for(int i = 1, l, r; i <= m; ++i) {
			scanf("%d%d", &l, &r), l--;
			int ans = 0;
			for(int j = 0; j < 30; ++j) ans |= (c[r][j] > c[l][j]) << j;
			for(int j = 29; ~j; --j) if(z[r][j] > z[l][j]) {
				int t = lst[r][j];
				if(z[r][j] > z[l][j] + 1) {
					ans |= all(j + 1);
					break;
				}
				/*for(int k = j; ~k; --k) if(t & (1 << k)) {
					if(ans & (1 << k)) {
						ans |= all(k + 1);
						break;
					}
					ans |= 1 << k;
				}*/
				int w = t & ~ans;
				ans |= w, t -= w;
				if(t) ans |= all(lg(t));
			}
			printf("%d ", ans);
		}
		puts("");
	}
}

Solution2

设两部分分别为 \(f,g=y\)，考虑如何合并 (1) \(f\) 直接或合并 (2) \(g\) 在合并时，可以先做或，如果有重叠的位，将其中一个的这一位舍掉可以把下面的所有位都赋 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>

const int N = 2e5 + 10;

char buf[200000], *p1, *p2;
#define getchar() (((p1==p2)&&(p2=(p1=buf)+fread(buf,1,200000,stdin))),*p1++)
int rd() {
	int x = 0; char c;
	while(c = getchar(), c < 48);
	do x = x * 10 + (c - 48);
	while(c = getchar(), c > 47);
	return x;
}

int n, k;
int all(int n) { return (1 << n) - 1; }
int lg(int x) { return 31 - __builtin_clz(x); }
int uor(int x, int y) {
	int z = x | y;
	if(x & y) z |= all(lg(x & y));
	return z;
}
int f[N << 2], g[N << 2];
int sf, sg;

int main() {
	for(int T = rd(); T--; ){
		for(n = rd(), k = 1; k <= n + 1; k <<= 1);
		for(int i = 0; i < k; ++i) f[k + i] = g[k + i] = 0;
		for(int i = 1; i <= n; ++i) {
			int x = rd(), y = rd();
			int t = x & ~all(lg(x ^ y) + 1);
			f[k + i] = t, g[k + i] = y ^ t;
		}
		for(int i = k - 1; i; --i) {
			f[i] = f[i << 1] | f[i << 1 | 1];
			g[i] = uor(g[i << 1], g[i << 1 | 1]);
		}
		for(int m = rd(); m--; ) {
			sf = sg = 0;
			for(int l = rd() + k - 1, r = rd() + k + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
				if(~l & 1) {
					sf |= f[l ^ 1];
					sg |= uor(sg, g[l ^ 1]);
				}
				if(r & 1) {
					sf |= f[r ^ 1];
					sg |= uor(sg, g[r ^ 1]);
				}
			}
			printf("%d ", uor(sf, sg));
		}
		puts("");
	}
}