Codeforces Round #746 (Div. 2) - E. Bored Bakry

题意

image-20211006182828913.png

给定一个数组$\lbrace a_n \rbrace$,求出其中最长的$Good$序列的长度,若无则输出$0$。

当一段序列$\lbrace a_l,a_{l+1},\dots,a_{r-1},a_{r} \rbrace$满足$a_l \& a_{l+1} \& \dots a_{r-1} \& a_r > a_l \oplus a_{l+1}\oplus\dots\oplus a_{r-1} \oplus a_r$时,称为$Good$序列。

思路

刚开始看到这个题的时候,想的是线段树维护与运算的结果,然后再二分?

首先把$X \& Y$拆成$X \& Y=X|Y-X \oplus Y$​,异或运算可以用二十个前缀和来维护,而或运算可以开二十颗线段树维护区间最大值来实现(二十个是因为$2^{20} > 1e6$)。

然后考虑,如果要维护一个严格大于的关系,被选中的序列中,决定大小关系的那一位上的$1$一定要是连续的,只要被选中的序列中有某一位是$0$,那么相与之后得到的结果该位也一定是$0$​了,因此貌似可以二分。

时间复杂度理论上是$O(nlog^2n)$​,对这道题应该是过不去的。

以上均为口胡的猜想,还未写代码实现过…

后面没写出来,去评论区学习了更为精妙的$O(NlogN)$​的写法…

首先我们分析一下,什么情况下$\&$运算得到的结果要优于$\oplus$​运算。

假设$\&$​运算得到的结果的前$k-1$​位和$\oplus$​得到的结果的前$k-1$​位相同,而第$k$​位$\&$​运算得到$1$​,而$\oplus$​得到$0$​,其余位随意,那么核心就变成了什么情况下第$k$​位$\&$​运算能得到$1$​,而$\oplus$​运算能得到$0$​。

第K位

对于$\&$​运算,任一元素的对应位为$0$​,最后$\&$​出来的结果的对应位也为$0$​,因此若要使得第$k$​位为$1$​,序列中所有元素的第$k$​位也要为$1$​。在第$k$​位均为$1$​的情况下,为了使$\oplus$​运算得到$0$​,参与运算的元素个数要为偶数。

前K-1位

由上文对于第$K$​位情况的分析,我们知道元素个数为偶数

那么,假设$\&$​运算后得到的第$M(1\leq M\leq K-1)$​位结果为$1$​,就意味着偶数个$1$进行$\&$运算,此时$\oplus$运算得到的第$M$位结果为$0$,与假设前$k-1$​位相同冲突,因此$\&$运算得到的第$M$位的结果只能为$0$。

也就是说,前$K-1$位的$\oplus$运算后得到的结果$XOR$,与$\&$运算后得到的结果$AND$相同,且均为$0$​。

思路归纳

由此,题目中要找的序列条件可以拆分为:

  • 序列中的元素的前$k-1$位的异或和为$0$
  • 序列中的元素的第$k$位均为$1$
  • 序列中的元素个数一定为偶数

这样,问题就清晰多了,我们考虑枚举位置$k$。由于$2^{20}>1e6$,我们只需要枚举$20$个就可以了。

一般情况下,寻找前$k-1$位的异或和为$0$这一过程所需的时间复杂度是$O(N)$的,考虑优化。

首先对于连续一段数的异或和,我们考虑使用前缀和优化,设$pre[r]$为$1-r$中元素的异或和,则区间$[L,R]$的异或和可表示为$pre[R] \oplus pre[L-1]$。若$[L,R]$为一个合法序列,则有$pre[R] \oplus pre[L-1]=0$​。

更进一步的,我们有:$pre[R]=pre[L-1]$​。

有了这个条件,我们考虑对某一位置$R$,快速找到最近的$L$,满足$pre[R]=pre[L-1]$。

由于题目的值域很小$(1 \leq val \leq 1e6)$,我们可以开一个桶$last[val]=pos$,代表异或和$val$​出现的合法位置$pos$​。这样,目前枚举到第$R$个位置的元素时,满足异或和为$0$的序列$[L,R]$的位置$L=last[pre[R]]$。

此外,合法性主要是指枚举的第$k$位在当前序列中必须有连续的$1$,若出现了$0$则需要更新$last$,再更新答案。我们可以借助一个变量$l$,代表距离当前枚举到的位置$r$最近的$0$​的位置,以此来保障求的解的合法性。

满足了前两个条件后,还需要满足序列中的元素个数一定为偶数。可以设两个桶,即$last[2][val]$​,一个用来放奇数位的答案,一个用来放偶数位的答案。

整理完成之后可以编写代码如下。

Code

主要参考:https://codeforces.com/blog/entry/95583?#comment-847284

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
56
57
58
59
60
61
/* vegetable1024 | liushan.site | Maybe Lovely? */

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx", "sse2")
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 1000005
#define int long long
using namespace std;

clock_t START_TIME, END_TIME;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}

int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}

int n, ans, a[maxn], pre[maxn], last[2][maxn];
signed main(void)
{
n = read();
//START_TIME = clock();
for(int i = 1; i <= n; i++) a[i] = read();
for(int k = 20; k >= 1; k--){
memset(last, -1, sizeof(last));
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] ^ (a[i] >> k);
}
last[0][0] = 0;
int l = 0;
for(int r = 1; r <= n; r++){
if(a[r] & (1 << (k - 1))){
int lans = last[r & 1][pre[r]];
if(lans >= l)
ans = max(ans, r - lans);
}
else l = r;
if(last[r & 1][pre[r]] < l){
last[r & 1][pre[r]] = r;
}
}
}
printf("%lld\n", ans);
//END_TIME = clock();
//printf("%.5lf ms\n", (double)(END_TIME - START_TIME) / CLOCKS_PER_SEC * 1000);
return 0;
}

乱七八糟

寄了,早知道这把去写$C$和$D$了,想$B$想麻了(

如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ