AC日记——「SCOI2016」美味 LiBreOJ 2016

#2016. 「SCOI2016」美味

思路：

　　主席树；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxa 262143

#define maxn 200005

#define maxtree maxa*40

int n,m,ch[maxtree][],val[maxtree],L[maxtree],R[maxtree];

int root[maxn],mid[maxtree],tot;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void build(int &now,int l,int r)

{

    now=++tot,L[now]=l,R[now]=r;

    if(l==r) return;mid[now]=l+r>>;

    build(ch[now][],l,mid[now]);

    build(ch[now][],mid[now]+,r);

}

void add(int &now,int pre,int x)

{

    now=++tot,val[now]=val[pre]+,L[now]=L[pre],R[now]=R[pre];

    if(L[now]==R[now]) return ;mid[now]=mid[pre];

    if(x<=mid[now]) add(ch[now][],ch[pre][],x),ch[now][]=ch[pre][];

    else add(ch[now][],ch[pre][],x),ch[now][]=ch[pre][];

}

bool query(int now,int pre,int l,int r)

{

    if(L[now]>=l&&R[now]<=r) return (val[now]-val[pre])?true:false;

    if(l<=mid[now]) if(query(ch[now][],ch[pre][],l,r)) return true;

    if(r>mid[now]) if(query(ch[now][],ch[pre][],l,r)) return true;

    return false;

}

int solve(int now,int pre,int deep,int b,int x,int l,int r)

{

    if(deep<) return ;int mi=l+r>>;

    if(b<(<<deep))

    {

        if(query(root[now],root[pre],max(,mi+-x),r-x)) return solve(now,pre,deep-,b,x,mi+,r)+(<<deep);

        else return solve(now,pre,deep-,b,x,l,mi);

    }

    else

    {

        if(mi-x<||query(root[now],root[pre],max(l-x,),mi-x)) return solve(now,pre,deep-,b-(<<deep),x,l,mi)+(<<deep);

        else return solve(now,pre,deep-,b-(<<deep),x,mi+,r);

    }

}

int main()

{

    freopen("data.txt","r",stdin);

    in(n),in(m),build(root[],,maxa);int pos,b,x,l,r;

    for(int i=;i<=n;i++) in(pos),add(root[i],root[i-],pos);

    while(m--) in(b),in(x),in(l),in(r),printf("%d\n",solve(r,l-,,b,x,,maxa));

    return ;

}