Codeforces 1100F(离线线性基 or 在线线性基+贪心)

传送门

 

参考资料:

  [1]:在线线性基

  [2]:离线线性基

  [3]:离线线性基

 

•题意

  给你 n 个数,m 次询问;

  每次询问给定一个区间 $l,r$,求 $a_{l \cdots r}$ 异或的最大值;

•线段树+线性基

  参考了一下资料[1],学会了如何将线性基和线段树结合;

  虽然在此题中会 TLE,但是却学到了不少东西;

  首先,在建树的时候,将叶节点上的值插入到线性基中;

  在回溯的时候,通过 Merge 操作,将 pos 的儿子节点的线性基合并到 pos 的线性基上;

  类似于常规线段树中的 pushUp 操作;

  此算法可以用来做这道题:洛谷P4839

•Code(线段树TLE版本)

Codeforces 1100F(离线线性基 or 在线线性基+贪心)
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define ls(x) (x<<1)
  4 #define rs(x) (x<<1|1)
  5 const int maxn=5e5+50;
  6  
  7 int n,q;
  8 int a[maxn];
  9 struct Seg
 10 {
 11     int l,r;
 12     int a[25];
 13     int mid(){return l+((r-l)>>1);}
 14     void Insert(int x)
 15     {
 16         for(int i=20;i >= 0;--i)
 17         {
 18             if(x&(1<<i))
 19             {
 20                 if(!a[i])
 21                 {
 22                     a[i]=x;
 23                     return ;
 24                 }
 25                 x ^= a[i];
 26             }
 27         }
 28     }
 29     int Max()
 30     {
 31         int ans=0;
 32         for(int i=20;i >= 0;--i)
 33             ans=max(ans,ans^a[i]);
 34         return ans;
 35     }
 36 }seg[maxn<<2];
 37  
 38 Seg Marge(Seg a,Seg b)
 39 {
 40     Seg tmp=b;
 41     for(int i=0;i <= 20;++i)
 42         if(a.a[i])
 43             tmp.Insert(a.a[i]);
 44     return tmp;
 45 }
 46 void buildSeg(int l,int r,int pos)
 47 {
 48     seg[pos].l=l;
 49     seg[pos].r=r;
 50  
 51     if(l == r)
 52     {
 53         seg[pos].Insert(a[l]);
 54         return ;
 55     }
 56  
 57     int mid=l+((r-l)>>1);
 58     buildSeg(l,mid,ls(pos));
 59     buildSeg(mid+1,r,rs(pos));
 60  
 61     seg[pos]=Marge(seg[ls(pos)],seg[rs(pos)]);
 62     seg[pos].l=l;///此处要注意,因为Marge返回的结果未给l,r赋值
 63     seg[pos].r=r;
 64 }
 65 Seg Query(int l,int r,int pos)
 66 {
 67     if(seg[pos].l == l && seg[pos].r == r)
 68         return seg[pos];
 69  
 70     int mid=seg[pos].mid();
 71  
 72     if(r <= mid)
 73         return Query(l,r,ls(pos));
 74     else if(l > mid)
 75         return Query(l,r,rs(pos));
 76     else
 77         return Marge(Query(l,mid,ls(pos)),Query(mid+1,r,rs(pos)));
 78 }
 79 void Solve()
 80 {
 81     for(int i=1;i <= q;++i)
 82     {
 83         int l,r;
 84         scanf("%d%d",&l,&r);
 85  
 86         Seg ans=Query(l,r,1);
 87  
 88         printf("%d\n",ans.Max());
 89     }
 90 }
 91 int main()
 92 {
 93 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
 94     scanf("%d",&n);
 95     for(int i=1;i <= n;++i)
 96         scanf("%d",a+i);
 97     buildSeg(1,n,1);
 98  
 99     scanf("%d",&q);
100     Solve();
101  
102     return 0;
103 }
View Code

•离线线性基

  学会了和线段树结合后,看了看正解 线性基+贪心,果然,看不懂;

  放弃了这个解法,找了几篇离线线性基的做法(资料[2],[3]);

  大致做法是,将所有询问收集起来,并按照 r 升序排列;

  边插入 ai 边判断当前的 i 是否为当前询问的右端点;

  插入的时候,记录两个数值 base[ i ] , p[ i ],表示第 p[ i ] 个数 $a_{p_i}$ 在通过 Insert() 操作时,插入的时候插到了 base[ i ] 中;

  每次插入第 i 个数 ai 时,优先让高位的 1 用当前的位置来表示,这样可以保证高位的 1 对应的 base 值可以对最大值有贡献;

•Code(离线)

Codeforces 1100F(离线线性基 or 在线线性基+贪心)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5e5+50;
 4  
 5 int n,m;
 6 int a[maxn];
 7 struct Query
 8 {
 9     int l,r;
10     int pos;
11     bool operator < (const Query &obj) const
12     {
13         return r < obj.r;
14     }
15 }q[maxn];
16 int base[30];
17 int p[30];
18 int ans[maxn];
19  
20 void Insert(int pos,int x)
21 {
22     for(int i=20;i >= 0;--i)
23     {
24         if(x&(1<<i))
25         {
26             if(!base[i])
27             {
28                 base[i]=x;
29                 p[i]=pos;
30                 return ;
31             }
32             else if(pos > p[i])///第i位的base[i]优先让p大的表示
33             {
34                 swap(base[i],x);
35                 swap(p[i],pos);
36             }
37             x ^= base[i];
38         }
39     }
40 }
41 int Max(int k)
42 {
43     int l=q[k].l;
44     int r=q[k].r;
45  
46     int ans=0;
47     ///查询时,保证p大的高位base优先考虑
48     for(int i=20;i >= 0;--i)
49         if(p[i] >= l && p[i] <= r)
50             ans=max(ans,ans^base[i]);
51     return ans;
52 }
53 void Solve()
54 {
55     sort(q+1,q+m+1);
56  
57     int k=1;
58     for(int i=1;i <= n;++i)
59     {
60         Insert(i,a[i]);
61 
62         while(i == q[k].r)
63         {
64             
65             ans[q[k].pos]=Max(k);
66             k++;
67         }
68     }
69  
70     for(int i=1;i <= m;++i)
71         printf("%d\n",ans[i]);
72  
73     return ;
74 }
75 int main()
76 {
77 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
78     scanf("%d",&n);
79     for(int i=1;i <= n;++i)
80         scanf("%d",a+i);
81  
82     scanf("%d",&m);
83     for(int i=1;i <= m;++i)
84     {
85         scanf("%d%d",&q[i].l,&q[i].r);
86         q[i].pos=i;
87     }
88  
89     Solve();
90  
91     return 0;
92 }
View Code

•在线线性基

  学会了离线的,再看资料[1]的正解代码时,理解起来容易了不少;

•Code(在线)

Codeforces 1100F(离线线性基 or 在线线性基+贪心)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5e5+50;
 4 
 5 int n,q;
 6 int a[maxn];
 7 int base[maxn][30];
 8 int p[maxn][30];
 9 
10 void Insert(int pos,int x,int k)
11 {
12     for(int i=20;i >= 0;--i)
13     {
14         if(x&(1<<i))
15         {
16             if(!base[k][i])
17             {
18                 base[k][i]=x;
19                 p[k][i]=pos;
20             }
21             else if(pos > p[k][i])
22             {
23                 swap(pos,p[k][i]);
24                 swap(x,base[k][i]);
25             }
26             x ^= base[k][i];
27         }
28     }
29 }
30 int Max(int l,int r)
31 {
32     int ans=0;
33     for(int i=20;i >= 0;--i)
34         if(p[r][i] >= l)
35             ans=max(ans,ans^base[r][i]);
36     return ans;
37 }
38 void Solve()
39 {
40     for(int i=1;i <= n;++i)
41     {
42         memcpy(base[i],base[i-1],sizeof(base[i-1]));
43         memcpy(p[i],p[i-1],sizeof(p[i-1]));
44 
45         Insert(i,a[i],i);
46     }
47 
48     while(q--)
49     {
50         int l,r;
51         scanf("%d%d",&l,&r);
52 
53         printf("%d\n",Max(l,r));
54     }
55 }
56 int main()
57 {
58     scanf("%d",&n);
59     for(int i=1;i <= n;++i)
60         scanf("%d",a+i);
61     scanf("%d",&q);
62 
63     Solve();
64 
65     return 0;
66 }
View Code

 

上一篇:Java 中 如何将一个字符重复n遍


下一篇:主席树/线段树模拟归并排序+二分答案(好题)——hdu多校第4场08