[01字典树]求序列完美度(求区间最大异或值)

https://nanti.jisuanke.com/t/15531

解题关键：01字典树模板，用字典树保存每个数的二进制表示，从而动态维护区间上的最大异或值，注意添加和删除都可以用于一个change函数表示。

复杂度：$O(nlog n + {n^2}log n)$

 1 #include<bits/stdc++.h>
 2 #define maxn 1005
 3 #define inf 0x3f3f3f3f
 4 using namespace std;
 5 typedef long long ll;
 6 int a[maxn];
 7 int num[32*maxn][2];
 8 int node[32*maxn][2];
 9 int val[32*maxn];
10 int sum,ans,l,r,anss,s;
11 
12 void init(){
13     sum=1;
14     ans=-inf;
15     memset(num,0,sizeof num);
16     memset(node,0,sizeof node);
17     memset(val,0,sizeof val);
18 }
19 
20 void change1(int m,int x){
21     int pos=0;
22     for(int i=30;i>=0;i--){
23         int j=x>>i&1;
24         num[pos][j]+=m;
25         if(node[pos][j]) pos=node[pos][j];
26         else{
27             memset(node[sum],0,sizeof node[sum]);
28             node[pos][j]=sum++;
29             pos=node[pos][j];
30         }
31     }
32     val[pos]=x;
33 }
34 
35 int search1(int L,int R,int x){
36     int pos=0;
37     int w=0;
38     
39     for(int i=30;i>=0;i--){
40         int j=x>>i&1;
41         if(num[pos][!j]){
42             w+=1<<i;
43             pos=node[pos][!j];
44         }
45         else    pos=node[pos][j];
46     }
47     if(w>ans) ans=w,l=L,r=R,anss=val[pos];
48 }
49 
50 int main(){
51     int t,n;
52     cin>>t;
53     while(t--){
54         init();
55         cin>>n;
56         for(int i=1;i<=n;i++) cin>>a[i],change1(1,a[i]);
57         
58         for(int i=1;i<=n;i++){
59             s=0;
60             for(int j=i;j<=n;j++){
61                 s+=a[j];
62                 change1(-1,a[j]);
63                 int w=search1(i,j,s);
64             }
65             
66             for(int j=i;j<=n;j++) change1(1,a[j]);
67         }
68         cout<<l<<" "<<r<<" "<<anss<<" "<<ans<<endl;
69     } 
70 }