https://vjudge.net/contest/436481

A - XOR

 

题意：给定一个数组和 K，多次询问，每次询问给定L，R，求区间 [L,R][L,R] 的子序列，满足子序列的异或和与 K 的按位或最大。输出这个最大值。

线段树+线性基

由于要与 K 按位或，所以可以不考虑 K 中为 1 的位，所以先全都去掉。问题变为求子序列的异或和最大。

要求的是最大异或和，考虑线性基。询问的是多个不同的区间，显然不能每次重新建线性基。但是也没法一边插入一边删除，所以考虑不删除，而是用几个区间拼成需要的区间。

线段树维护区间的线性基，当合并两个节点时合并这两个区间的线性基，即把其中一个的所有基插入另一个中。

询问时先用线段树拼出区间 [L,R][L,R] 的线性基，再用这个线性基求出最大异或和。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = false;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> P;
#define ll long long

const int maxn = 2e5 + 5;
const int N = maxn;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-13;

#define Assert(x) if (!(x)) cout << 1 / 0;

int T;
int n,q,k;
int a[N];
#define mid ((l+r)>>1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
int b[30];
int tr[N<<2], tb[N<<2][30];
void ins(int x, int* b){
    for(int i=29;i>=0;i--){
        if(x>>i&1){
            if(!b[i]){b[i]=x;break;}
            x^=b[i];
        }
    }
}
void merge(int* tb1, int* tb2, int* b){
    for(int i=0;i<30;i++)b[i]=tb2[i];
    for(int i=29;i>=0;i--){
        ins(tb1[i], b);
    }
}
void up(int rt){
    merge(tb[rt<<1], tb[rt<<1|1], tb[rt]);
}
void build(int l, int r, int rt){
    if(l == r){
        for(int i=29;i>=0;i--)tb[rt][i]=0;
        for(int i=29;i>=0;i--){
            if(a[l]>>i&1){
                tb[rt][i]=a[l];
                break;
            }
        }
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}
void qry(int ql, int qr, int l, int r, int rt){
    if(ql <= l && qr >= r){
        merge(tb[rt], b, b);
        return;
    }
    if(ql<=mid)qry(ql,qr,lson);
    if(qr>mid)qry(ql,qr,rson);
}
int main() {
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &q, &k);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]), a[i]&=(~k);
        build(1, n, 1);
        while(q--){
            int l, r;
            scanf("%d%d", &l, &r);
            for(int i=0;i<30;i++)b[i]=0;
            qry(l, r, 1, n, 1);
            int ans=0;

            for(int i=29;i>=0;i--){
                if(b[i])ans=max(ans, ans^b[i]);
            }
            printf("%d\n", ans | k);
        }
    }
    return 0;
}

 

K - LOVER II

 

题意：给定长为 nn 的数组 aa，长为 mm 的数组 bb，规定仅当 ai+bj≥ka_i+b_j\ge k 时，aia_i 和 bjb_j 可以配对，多次询问，每次询问给定 L,RL,R，问能否只用 b[L],b[L+1],⋯ ,b[R]b[L],b[L+1],\cdots,b[R]，使得 aa 中每个元素都有配对。

线段树+尺取法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> P;
#define ll long long

const int maxn = 2e5 + 5;
const int N = maxn;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-13;

#define Assert(x) while (!(x));

int tree[maxn<<2], lazy[maxn<<2];

int n, m, t, a[maxn], b[maxn], k;


void build(int node, int l, int r)
{
    lazy[node] = 0;
    if(l == r)
    {
        tree[node] = - n - 1 + l;
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node *2 + 1, mid + 1, r);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

void push_down(int node)
{
    if(lazy[node])
    {
        tree[node*2] -= lazy[node];
        tree[node*2+1] -= lazy[node];
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
        lazy[node] = 0;
    }
}

int query(int node, int l, int r, int x, int y)
{
    if(x <= l && y >= r)
        return tree[node];

    push_down(node);
    int mid = (l + r) / 2;
    int ans = INF;
    if(x <= mid)  ans = min(ans, query(node * 2, l, mid, x, y));
    if(y > mid)  ans = min(ans, query(node * 2 + 1, mid + 1, r, x, y));
    return ans;
}

void update(int node, int l, int r, int x, int y, int c)
{
    if(x <= l && y >= r)
    {
        tree[node] -= c;
        lazy[node] += c;
        return;
    }

    push_down(node);
    int mid = (l + r) / 2;
    if(x <= mid)  update(node * 2, l, mid, x, y, c);
    if(y > mid) update(node * 2 + 1, mid + 1, r, x, y, c);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

int pro[maxn];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        int tmp;
        scanf("%d %d %d", &n, &m, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
        for(int i = 1; i <= n; i++) a[i] = k - a[i];
        sort(a + 1, a + 1 + n);
        for(int i = 1; i <= m; i++)
        {
            tmp = upper_bound(a + 1, a + 1 + n, b[i]) - a;
            b[i] = tmp - 1;
        }
        build(1, 1, n);
        int L = 1, R = 1;
        while(L <= m)
        {
            while(R <= m && query(1, 1, n, 1, n) < 0)
            {
                if(b[R] > 0) update(1, 1, n, 1, b[R], -1);
                R++;
            }
            if(query(1, 1, n, 1, n) >= 0)
            {
                pro[L] = R - 1;
                if(b[L] > 0) update(1, 1, n, 1, b[L], 1);
                L++;
                continue;
            }
            break;
        }
        for(int i = L; i <= m; i++)  pro[i] = -1;
        int q, l, r;
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d %d", &l, &r);
            if(pro[l] < 0 || pro[l] > r) printf("0\n");
            else printf("%d\n", 1);
        }
    }
}