题意

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$想麻了（