LibreOJ 2016 「SCOI2016」美味

这个题目的思路比较清奇？
一直想着用 Trie 来做，然而……

首先按位贪心是显然的，如果没有 xi 的限制，可持久化 Trie 完事。
但是现在有了一个偏移量 xi，直接在 Trie 的结构上不太好做。

那么——我们可以用两只 log 来解决，一只用来按位贪心，一只用来检查是否合法。
后者使用主席树。

即，从高位到低位枚举，然后每次在主席树上检查 [li,ri] 区间内是否有如此的数（查询时减去 xi）。

代码：

#include <cstdio>
using namespace std;
const int N = 2e5;
const int C = 1e5;
const int LG = 18;
int n,m,a[N + 5],ans;
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],++seg[p = tot].sum;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
    r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),insert(a[i],rt[i] = rt[i - 1],0,C);
    int b,x,l,r;
    while(m--)
    {
        scanf("%d%d%d%d",&b,&x,&l,&r),ans = 0;
        for(register int i = LG;i;--i)
        {
            ans += ((((b >> i - 1) & 1) ^ 1) << i - 1);
            if(!(query(ans - x,ans + (1 << i - 1) - 1 - x,rt[r],0,C) - query(ans - x,ans + (1 << i - 1) - 1 - x,rt[l - 1],0,C)))
                ans ^= 1 << i - 1;
        }
        printf("%d\n",ans ^ b);
    }
}