bzoj 4571 [Scoi2016]美味——主席树

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4571

按位考虑，需要的就是一个区间；比如最高位就是（2^k -x)。

对于不是最高位的位置该怎么考虑？其实之前位置如果能或不能匹配上，也就相当于指定了之前的位上的是0还是1；把是1的位累计进一个变量里，加到区间的边界上就行了！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=2e5+,M=1e5+,K=N*;

int n,m,mx,a[N],rt[N],tot,sm[K],ls[K],rs[K];

int ans,lj,lo,hi,bin[];

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void build(int &cr,int pre,int l,int r,int v)

{

    cr=++tot; ls[cr]=ls[pre]; rs[cr]=rs[pre];

    sm[cr]=sm[pre]+;

    if(l==r) return; int mid=l+r>>;

    if(v<=mid) build(ls[cr],ls[pre],l,mid,v);

    else build(rs[cr],rs[pre],mid+,r,v);

}

bool query(int cr,int pre,int l,int r,int L,int R)

{

    if(l>=L&&r<=R) return sm[cr]-sm[pre];

    int mid=l+r>>; bool fg=;

    if(L<=mid) fg=query(ls[cr],ls[pre],l,mid,L,R);

    if(!fg&&mid<R) fg=query(rs[cr],rs[pre],mid+,r,L,R);

    return fg;

}

void init()

{

    bin[]=;

    for(int i=;i<=;i++) bin[i]=bin[i-]<<;

}

int main()

{

    n=rdn(); m=rdn(); init();

    for(int i=;i<=n;i++) a[i]=rdn(),mx=max(mx,a[i]);

    for(int i=;i<=n;i++)

        build(rt[i],rt[i-],,mx,a[i]);

    for(int i=,b,x,l,r;i<=m;i++)

    {

        b=rdn(); x=rdn(); l=rdn(); r=rdn();

        ans=;  lj=;

        for(int j=;j>=;j--)

        {

            if(b&bin[j]) {lo=lj; hi=lj+bin[j]-;}

            else {lo=lj+bin[j]; hi=lj+bin[j+]-;}

            hi-=x; lo-=x;

            hi=min(hi,mx); lo=max(lo,);

            if(lo<=hi&&query(rt[r],rt[l-],,mx,lo,hi))

                lj+=(b&bin[j]?:bin[j]),ans+=bin[j];

            else lj+=(b&bin[j]?bin[j]:);

        }

        printf("%d\n",ans);

    }

    return ;

}