「SCOI2016」美味 - 贪心 + 主席树

一家餐厅有道菜，编号，大家对第道菜的评价值为（）。有位顾客，第位顾客的期望值为，而他的偏好值为。因此，第位顾客认为第道菜的美味度为（表示异或运算）。第位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第道到第道中选择。请你帮助他们找出最美味的菜。

链接

BZOJ 4571

题解

先考虑问题的一个简化版本 —— 给一个序列，第个询问为。这个问题可以使用 Trie 树存储序列的所有数，从高位到低位贪心解决。

Trie 树上从高位到低位贪心的实质是，对于前面若干位考虑过的值为，考虑第位，查询序列中是否有数在和这两个区间内，所以我们可以把 Trie 树换成权值线段树。这一步转化十分关键。

继续考虑一个更接近原问题的简化版本 —— 给一个序列，第个询问为。即，每次查询前对整个序列加上一个数。考虑到权值线段树无法整体将所有值加上一个数（因为整体右移整棵树会改变树的形态），一个显然的思路是每次查询和这两个区间时，将要查询的区间整体左移，即改为查询和这两个区间。

现在回到原问题，给一个序列，第个询问为。我们只需要在前一个问题的基础上，把普通的线段树改为主席树即可。

代码

#include <cstdio>

const int MAXN = 2e5;
const int MAXM = 1e5;
const int HIGHEST_BIT = 17;

struct PSegT {
    struct SegT {
        int l, r;
        SegT *lc, *rc;
        int cnt;

        SegT() {}
        SegT(int l, int r, SegT *lc, SegT *rc, int cnt) : l(l), r(r), lc(lc), rc(rc), cnt(cnt) {}
        SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), cnt(lc->cnt + rc->cnt) {}

        int query(int l, int r) {
            if (l > this->r || r < this->l) return 0;
            else if (l <= this->l && r >= this->r) return cnt;
            else return lc->query(l, r) + rc->query(l, r);
        }
    } *rt[MAXN + 1], *null;

    PSegT() {
        null = new SegT(-1, -1, NULL, NULL, 0);
        rt[0] = null->lc = null->rc = null;
    }

    SegT *insert(SegT *v, int l, int r, int x) {
        if (l == r) return new SegT(l, r, null, null, v->cnt + 1);
        int mid = l + (r - l) / 2;
        if (x > mid) return new SegT(l, r, v->lc, insert(v->rc, mid + 1, r, x));
        else return new SegT(l, r, insert(v->lc, l, mid, x), v->rc);
    }

    void build(int *a, int n) {
        for (int i = 1; i <= n; i++) {
            rt[i] = insert(rt[i - 1], 0, MAXN - 1, a[i]);
        }
    }

    int maxAddXor(int ql, int qr, int add, int x) {
        SegT *tr = rt[qr], *tl = rt[ql - 1];
        int ans = 0, xorWith = 0;
        for (int i = HIGHEST_BIT; i >= 0; i--) {
            int k = 1 << i;

            if (k & x) { // The k-th lower bit of `x` is 1
                bool canZero = tr->query(xorWith - add, xorWith + k - 1 - add) - tl->query(xorWith - add, xorWith + k - 1 - add) != 0;
                if (canZero) {
                    ans |= k;
                } else {
                    xorWith |= k;
                }
            } else {     // The k-th lower bit of `x` is 0
                bool canOne = tr->query(xorWith + k - add, xorWith + 2 * k - 1 - add) - tl->query(xorWith + k - add, xorWith + 2 * k - 1 - add) != 0;
                if (canOne) {
                    ans |= k;
                    xorWith |= k;
                }
            }
        }
        return ans;
    }
} ps;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    static int a[MAXN + 1];
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    ps.build(a, n);

    while (m--) {
        int b, x, l, r;
        scanf("%d %d %d %d", &b, &x, &l, &r);
        printf("%d\n", ps.maxAddXor(l, r, x, b));
    }

    return 0;
}