题目链接
题目分数：2400

题目描述

输入$T(≤1e5)$表示$T$组数据。所有数据的$n$之和$≤3e5$。每组数据输入$n(2≤n≤3e5)$和长为$n$ 的数组a(O<a[i]≤1e9)，下标从0开始。构造一个严格单调递增的，元素范围在$[0,n-1]$的下标数组id。要求id中的所有相邻元素i和j，都满足$a[i]XOR j<a[i] XOR i$。例如$a=[5,2,4,3,1]$，构造$id=[1,2,4]$，满足$a[1]XOR 2<a[2]XOR 1$以及$a[2]XOR 4<a[4]XOR 2$。输出id的最大长度。

样例

输入样例1

3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3

输出样例1

2
3
6

算法

(数位枚举+map) $O(30*n)$

这道题目看起来很像单调上升子序列模型，但是有异或条件，所以不能直接做。那么熟悉异或的朋友们都知道，如果这个式子是等式的话，那么两边都可以异或上$i*j$，这样式子就变成了w[i]^i=w[j]^j，但是可惜是大于号，那么就没有这个性质了。那么我们想一个数怎么样才会大于另一个数呢？在二进制下，一个数大于另一个数，必定是在第$k$位之前，都相等，在第$k$位时，第一个数大于第二个数。
那么在这道题中，想法类似，我们可以枚举位数$k$，表示前$(k+1)$位相等为$g$，在第$k$位时当前的数大于另一个数。那么在看前$(k+1)$位时，两边相等，所以可以直接像上面一样化简，这样就简化了题目。我们用$f[k][g][p][q]$表示当前枚举到第$k$位，前$(k+1)$位是$g$，$p$是当前元素第$k$位$(0或1)$，$q$是当前下标第$k$位$(0或1)$。我们在枚举第$k$位时，g = (w[ i ] ^ i)>>(k + 1)，但是通过题目给的公式我们如果想让不等式成立，那么当前第$k$位$w[i]$与$j$应该是相反的，$w[j]$和$i$是相同的。等枚举完后，在更新$f$。
但是这道题我用$map$时反复被卡，最后只能使用$trie$树，使用$trie$就比较简单了，因为$trie$自带大小关系，我们只需要从大到小枚举，就可以维护前$(k+1)$相等这个关系。最后我用$memset$时在$test11$也被卡了，无奈只能将数组开大，每次将起始点换成上一次的值$+1$.

C++ 代码

// 我用map被卡了，memset用也被卡了，这里用的trie树

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 3e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int tr[N*31][2];
int f[N*31][2][2];
int idx;

void solve()
{
    scanf("%d", &n);
    int res = 0;
    int start = idx + 1;
    idx++;
    for(int i=0;i<n;i++){
        int u;
        scanf("%d", &u);
        int maxn = 0, p = start;
        for(int j=29;~j;j--){
            int t = (u^i) >> (j+1) & 1;
            if(!tr[p][t]) break;
            maxn = max(maxn, f[tr[p][t]][i>>j&1][(u>>j&1)^1]);
            p = tr[p][t];
        }
        maxn++;
        res = max(res, maxn);
        p = start;
        for(int j=29;~j;j--){
            int t = (u^i) >> (j+1) & 1;
            if(!tr[p][t]) tr[p][t]=++idx;
            auto &o = f[tr[p][t]][u>>j&1][i>>j&1];
            o = max(o, maxn);
            p = tr[p][t];
        }
    }
    printf("%d\n", res);
}

int main()
{
    int T;
    scanf("%d", &T);   
    while(T--)
    {
        solve();
    }

    return 0;
}