(luogu3293) 美味 (SCOI2016)

发表于 分类于 ， ，

原题链接

思路:

先将 \(a_j+x_i\) 看作一个整体，与 \(b_i\) 求最大异或和.

求最大异或和使用贪心的方法，即从高位往低位枚举， 尽量使某一位异或值为 1.

假设前 \(i-1\) 位处理完后结果为 \(ans\), 则第 \(i\) 位为 0 时 \(a+x\) 取值范围是 \([ans,ans+2^{i}-1]\), 为 1 时取值范围是 \([ans+2^i,ans+2^{i+1}-1]\).

于是对于 \(a\), 两个取值范围为 \([ans-x,ans+2^{i}-x-1]\) 和 \([ans+2^i-x,ans+2^{i+1}-x-1]\)

问题便转换为数组区间 \([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
94
95
96
97
98
99
100
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;
typedef long long LL;
const int Mn(200500);

template<typename T>
void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + (c-'0');
        c = getchar();
    }
}

int n,m;

struct tnd {    //主席树结点, 使用动态开点
    int v;
    tnd *ls,*rs;
}*rts[Mn],*nil,mem[Mn*20];  //主席树根结点, 自定义NULL, 可用空间
void init_nil() {   //初始化NULL
    nil = mem;
    *nil = (tnd) {0,nil,nil};
}
tnd* new_tnd(tnd x) {   //开辟新空间
    static int memcnt = 0;
    mem[++memcnt] = x;
    return mem+memcnt;
}

void mdf(tnd*& rt,int l,int r,int mp) { //主席树上可持久化更新
    rt = new_tnd(*rt);  //复制结点
    ++rt->v;
    if(l==r) {
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        mdf(rt->ls,l,mid,mp);
    } else {
        mdf(rt->rs,mid+1,r,mp);
    }
}
int qry(tnd* rt,int l,int r,int ql,int qr) {    //查询
    if(rt==nil || qr<l || ql>r) {
        return 0;
    }
    if(l>=ql && r<=qr) {
        return rt->v;
    }
    int mid((l+r)/2);
    int ret(0);
    if(ql<=mid) {
        ret += qry(rt->ls,l,mid,ql,qr);
    }
    if(qr>mid) {
        ret += qry(rt->rs,mid+1,r,ql,qr);
    }
    return ret;
}


int main() {
    init_nil(); //初始化
    rts[0] = nil;
    qrd(n), qrd(m);
    int tl(0),tr(100000);   //值域范围
    for(int i(1);i<=n;++i) {
        int a; qrd(a);
        rts[i] = rts[i-1];
        mdf(rts[i],tl,tr,a);    //预处理
    }
    while(m--) {
        int b,x,ql,qr;
        qrd(b), qrd(x), qrd(ql), qrd(qr);
        int ans(0);
        for(int i(17);i>=0;--i) {
            if(b&(1<<i)) {  //b第i位为1
                int qret = qry(rts[qr],tl,tr,ans-x,(ans|(1<<i))-x-1) - qry(rts[ql-1],tl,tr,ans-x,(ans|(1<<i))-x-1); //第i位为0是否有值
                if(qret==0) {
                    ans |= (1<<i);
                }
            } else {
                int qret = qry(rts[qr],tl,tr,(ans|(1<<i))-x,(ans|((1<<(i+1))-1))-x) - qry(rts[ql-1],tl,tr,(ans|(1<<i))-x,(ans|((1<<(i+1))-1))-x);   //第i位为1是否有值
                if(qret>0) {
                    ans |= (1<<i);
                }
            }
        }
        printf("%d\n",ans^b);
    }
    return 0;
}