牛客练习赛53E 老瞎眼 pk 小鲜肉(线段树)

链接：https://ac.nowcoder.com/acm/contest/1114/E
来源：牛客网
题目：
老瞎眼有一个长度为 n 的数组 a,为了为难小鲜肉，他准备了 Q 次询问，每次给出一个区间[L,R],他让小鲜肉寻找一对 l,r 使L<=l<=r<=R 且 a[l]^a[l+1]^a[l+2]...^a[r]=0,老瞎眼只让他回答r-l+1 最小是多少，若没有符合条件的 l,r 输出”-1”。

解题思路：预处理出对于每个位置i找到左边离i最近的位置j使得a[j]^a[j+1]^a[j+2]^……a[i]=0记为pre[i],将询问按r从小到大排序，然后从1-n处理每个位置，对于位置i，在线段树上将pre[i]的值更新为i-pre[i]+1,然后查询【Q[i].l，Q[i].r】的最小值

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=5e5+;

int n,q;

int pos[maxn<<],pre[maxn],tree[maxn<<],ans[maxn];

struct node{

    int l,r,id;

    bool operator<(const node x)const{

        return r<x.r;

    }

}Q[maxn];

void update(int pos,int val,int l,int r,int rt){

    if(l==r){

        tree[rt]=min(tree[rt],val);

        return;

    }

    int mid=(l+r)>>;

    if(pos<=mid) update(pos,val,l,mid,rt<<);

    else update(pos,val,mid+,r,rt<<|);

    tree[rt]=min(tree[rt<<],tree[rt<<|]);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r){

        return tree[rt];

    }

    int ans=0x3f3f3f3f,mid=(l+r)>>;

    if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<));

    if(R>mid) ans=min(ans,query(L,R,mid+,r,rt<<|));

    return ans;

}

int main(){

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

    int sum=;

    for(int i=;i<=*;i++){

        pos[i]=-;

        tree[i]=0x3f3f3f3f;

    }

    pos[]=;

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

        int x;

        scanf("%d",&x);

        sum^=x;

        if(pos[sum]!=-){

            pre[i]=pos[sum]+;

        }else pre[i]=-;

        pos[sum]=i;

    }

    for(int i=;i<=q;i++){

        scanf("%d%d",&Q[i].l,&Q[i].r);

        Q[i].id=i;

    }

    sort(Q+,Q++q);

    int cnt=;

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

        if(pre[i]!=-) update(pre[i],i-pre[i]+,,n,);

        while(Q[cnt].r==i){

            ans[Q[cnt].id]=query(Q[cnt].l,Q[cnt].r,,n,);

            cnt++;

        }

    }

    for(int i=;i<=q;i++){

        if(ans[i]>n)puts("-1");

        else printf("%d\n",ans[i]);

    }

    return ;

}

巴特西

牛客练习赛53E 老瞎眼 pk 小鲜肉(线段树)

最新文章

热门文章