F. Ivan and Burgers（线性基，离线）

题目链接：http://codeforces.com/contest/1100/problem/F

题目大意：首先输入n，代表当前有n个数，然后再输入m，代表m次询问，每一次询问是询问区间[l,r]，这段区间内的数的最大异或值。

具体思路：贪心，我们按照右边界的大小进行排序，小的在上面，大的往下安排，然后每一次我们寻找1--> r区间内的线性基，如果当前的线性基能往后移动，我们就选取后面的这个线性基（因为我们对输入的数据进行了排序，后面的r肯定是大的，所以我们将选取的线性基尽量的往后安排肯定是没有问题的，然后我们查询的时候，看一下当前位上有线性基的时候，先判断这个线性基取的时候是从哪个数里面取出来的，然后再看一下这个数是不是大于l的，如果是的话，这个线性基就是可用的，我们通过这些线性基寻找一个最大值就可以了）

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 const int maxn =5e5+;

 int sto[maxn],p[maxn],ans[maxn],ord[maxn];

 struct node

 {

     int l,r,id;

 } q[maxn];

 bool cmp(node t1,node t2)

 {

     return t1.r<t2.r;

 }

 void add(int num,int id)

 {

     for(int i=; i>=; i--)

     {

         if(((<<i)&num)==)

             continue;

         if(p[i]==)

         {

             p[i]=num;

             ord[i]=id;

             break;

         }

         if(ord[i]<id)//交换的时候都需要交换。

         {

             swap(ord[i],id);

             swap(num,p[i]);

         }

         num^=p[i];

     }

 }

 int query(int t)

 {

     int sum=;

     for(int i=; i>=; i--)

     {

         if(ord[i]>=t&&(sum^p[i])>sum)

             sum^=p[i];

     }

     return sum;

 }

 int main()

 {

     int n,m;

     scanf("%d",&n);

     for(int i=; i<=n; i++)

     {

         scanf("%d",&sto[i]);

     }

     scanf("%d",&m);

     for(int i=; i<=m; i++)

     {

         scanf("%d %d",&q[i].l,&q[i].r);

         q[i].id=i;

     }

     sort(q+,q+m+,cmp);

     int num=;

     for(int i=; i<=m; i++)

     {

         while(num<q[i].r)

             add(sto[++num],num);//将1-r都给压进去。

         ans[q[i].id]=query(q[i].l);

     }

     for(int i=; i<=m; i++)

     {

         printf("%d\n",ans[i]);

     }

     return ;

 }

巴特西

F. Ivan and Burgers（线性基，离线）

最新文章

热门文章