BZOJ 4571 美味

又一部SCOI血泪史。。。。

唉。

就是在这棵树上一遍又一遍跑嘛。

以后不要直接求答案啊。要最后再异或起来。

要学习简单的代码风格。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 200500

#define maxm 4005000

#define inf 262143

using namespace std;

int n,m,a[maxn],root[maxn],tot=,tree[maxm][],sum[maxm];

int b,x,l,r;

void insert(int last,int &now,int left,int right,int p)

{

    now=++tot;

    tree[now][]=tree[last][];tree[now][]=tree[last][];

    sum[now]=sum[last]+;

    if (left==right) return;

    int mid=(left+right)>>;

    if (p<=mid) insert(tree[last][],tree[now][],left,mid,p);

    else insert(tree[last][],tree[now][],mid+,right,p);

}

bool query(int last,int now,int left,int right,int l,int r)

{

    if ((left==l) && (right==r))

        return sum[now]-sum[last]>;

    int mid=(left+right)>>;

    if (r<=mid) return query(tree[last][],tree[now][],left,mid,l,r);

    else if (l>=mid+) return query(tree[last][],tree[now][],mid+,right,l,r);

    else return query(tree[last][],tree[now][],left,mid,l,mid)||query(tree[last][],tree[now][],mid+,right,mid+,r);

}

int main()

{

    scanf("%d%d",&n,&m);

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

        scanf("%d",&a[i]);

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

        insert(root[i-],root[i],,inf,a[i]);

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

    {

        scanf("%d%d%d%d",&b,&x,&l,&r);

        int ans=;

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

        {

            int tmp=b&(<<d);

            if (tmp)

            {

                int ll=max(ans-x,),rr=min(ans+(<<d)--x,inf);

                if (!query(root[l-],root[r],,inf,ll,rr)) ans^=(<<d);

            }

            else

            {

                ans^=(<<d);

                int ll=max(ans-x,),rr=min(ans+(<<d)-x-,inf);

                if (!query(root[l-],root[r],,inf,ll,rr)) ans^=(<<d);

            }

        }

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

    }

    return ;

}