「Bzoj 4571」「SCOI2016」美味 (主席树 + 按位贪心)

发表于 | 分类于 | | + s

BZOJ 4571
题意：给定$a_i​$，询问$m​$次$b,x,l, r​$, 求$\max(b \text{xor} (a_i+x))​$, $i \in [l, r]​$

这里有加法就不能用01Trie的方法了。然而我们还是可以按位贪心。
考虑贪心到第$i$位，当前已经贪了的$\text{ans}=a_i+x$，那么之后如果第$i$位填上了$1$，则答案范围为$[\text{ans} + 2^{i}, \text{ans} + 2^{i+1}-1]$
$0$同理为答案范围为$[\text{ans}, \text{ans} + 2^{i}-1]$
然后我们只需要看有没有$a_i$在这个范围即可判断能不能填了。
因为区间，所以用主席树来做。

注意主席树值域要开$2 \times 10^5$

知识点
1、异或的按位贪心。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5, MV = 300000 + 5;

    #define M ((l + r) >> 1)

    int n, m;
    int sz, rt[MAXN], lc[MAXN * 20], rc[MAXN * 20], sumv[MAXN * 20];

    void update(int pre, int &now, int l, int r, int p) {
        if (!now) now = ++sz, sumv[now] = 0;
        sumv[now] = sumv[pre] + 1;
        if (l == r) return ;
        if (p <= M) rc[now] = rc[pre], update(lc[pre], lc[now], l, M, p);
        else if (M < p) lc[now] = lc[pre], update(rc[pre], rc[now], M + 1, r, p);
    }
    int query(int x, int y, int l, int r, int u, int v) {
        if (u <= l && r <= v) return sumv[y] - sumv[x];
        int ans = 0;
        if (u <= M) ans += query(lc[x], lc[y], l, M, u, v);
        if (M < v) ans += query(rc[x], rc[y], M + 1, r, u, v);
        return ans;
    }

    void clean() {
        sz = 0;
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (int x, i = 1; i <= n; ++i) scanf("%d", &x), update(rt[i - 1], rt[i], 0, MV, x);
        for (int b, x, l, r, i = 1; i <= m; ++i) {
            scanf("%d%d%d%d", &b, &x, &l, &r);
            int ans = 0;
            for (int j = 18; j >= 0; --j) {
                int op = ((b >> j) & 1);
                int tl, tr;
                if (!op) tl = ans + (1 << j), tr = tl + (1 << j) - 1;
                else tl = ans, tr = tl + (1 << j) - 1;
                if (tr < 0 || tl > MV) { ans |= (op << j); continue ; }
                tl = max(0, tl - x), tr = min(MV, tr - x);
                if (tl > tr) { ans |= (op << j); continue ; }
                if (query(rt[l - 1], rt[r], 0, MV, tl, tr)) ans |= ((op ^ 1) << j); else ans |= (op << j);
            }
            printf("%d\n", ans ^ b);
        }

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------