Codeforces Round #532 (Div. 2) F. Ivan and Burgers(可持久化异或线性基+双指针)

86 阅读 0 评论 57 点赞

我是靠谱客的博主殷勤纸飞机，这篇文章主要介绍Codeforces Round #532 (Div. 2) F. Ivan and Burgers(可持久化异或线性基+双指针)，现在分享给大家，希望可以做个参考。

题意

给n个数，q组询问，每次询问l到r的最大异或和

思路来源

某cf奆神代码

题解

本来应该是线性基上分治的

这里一发基数+贪心也能过

真是神仙代码啊

双指针的经典应用：

对于每个询问[l,r]，r内放入询问的编号，

按r的增序，一边插入线性基一边解答，即固定右端点r的情况下，

如果线性基（因为线性基下标<=r）更靠右，显然是更有可能被包含在[l,r]的区间里的

在遇到相同高位的线性基的时候，用下标更靠右的p1与当前p2交换

让p1留在高位，现在就相当于进行p2遭遇已有线性基的p1之后，再向低位访问的过程

后续：这才知道，原来这就叫可持久化异或线性基

而且，因为搞离线之后，空间只需要用一倍而不用N倍了

代码

复制代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=512345;
int n,c[maxn],Q,l[maxn],p[33],q[33],res[maxn];
vector<int> g[maxn];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&c[i]);
    scanf("%d",&Q);
    for (int i=0;i<Q;++i) {
        int r;scanf("%d%d",&l[i],&r);
        g[r].push_back(i);//强制基数排序 
    }
    for (int t=1;t<=n;++t) {//按右端点增序插入 
        int x=c[t],r=t;
        for (int i=30;~i;--i) if (x>>i&1) {
            if (!p[i]) {
                p[i]=x;
                q[i]=r;//异或线性基的下标 尽量靠右 
                break;
            }
            if (q[i]<r) {//把一个r更大的线性基留在这里 原来的向低位找 
                swap(p[i],x);
                swap(q[i],r);
            }
            x^=p[i];
        }
        for (int o=0;o<(int)g[t].size();++o) {
            int k=g[t][o];//t对应的第k个询问 
            for (int i=30;~i;--i) if (q[i]>=l[k])//异或线性基的右界一定小于等于当前r 大于询问左界即合法 
                res[k]=max(res[k],res[k]^p[i]);
        }
    }
    for (int i=0;i<Q;++i) printf("%dn",res[i]);
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=512345;
int n,c[maxn],Q,l[maxn],p[33],q[33],res[maxn];
vector<int> g[maxn];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&c[i]);
    scanf("%d",&Q);
    for (int i=0;i<Q;++i) {
        int r;scanf("%d%d",&l[i],&r);
        g[r].push_back(i);//强制基数排序 
    }
    for (int t=1;t<=n;++t) {//按右端点增序插入 
        int x=c[t],r=t;
        for (int i=30;~i;--i) if (x>>i&1) {
            if (!p[i]) {
                p[i]=x;
                q[i]=r;//异或线性基的下标 尽量靠右 
                break;
            }
            if (q[i]<r) {//把一个r更大的线性基留在这里 原来的向低位找 
                swap(p[i],x);
                swap(q[i],r);
            }
            x^=p[i];
        }
        for (int o=0;o<(int)g[t].size();++o) {
            int k=g[t][o];//t对应的第k个询问 
            for (int i=30;~i;--i) if (q[i]>=l[k])//异或线性基的右界一定小于等于当前r 大于询问左界即合法 
                res[k]=max(res[k],res[k]^p[i]);
        }
    }
    for (int i=0;i<Q;++i) printf("%dn",res[i]);
    return 0;
}