【每日一题】12月17日题目精讲

题号 NC50444
名称 老瞎眼 pk 小鲜肉
来源 牛客练习赛53
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

作者：nagisa_菜鸡
看到题目，我想大家第一个想到的就是前缀异或和，因为这种询问一整段的异或和的一半都需要这样处理，不然复杂度太高。
之后，题目要询问的就是找到在区间[L,R]中的存在的点sum[l]==sum[r],使得r-l+1最小。若是考虑直接让值对应整个[l,r]区间则会很麻烦，所以，考虑转化为单点维护。
考虑单点维护，则有两个选择：要么放在l，要么放在r。
那么，我们先试个错误答案，若我们放在r，那么，我们在查询的时候就会遇到麻烦：我们在查询后面的点的时候，我们找不到一个方法确定查询到的值到底是不是属于[L,R]区间的，所以，不能选择r存储。
若选择了l，我们就有另一种方法了，那就是离线。我们将询问全部按照r排序，之后，我们枚举r（设现在枚举到的r为i），每次移动后，查询目前的sum[i]是否之前出现过，若有出现过，则将这个区间的贡献l-r+1作为l的贡献挂在点l处，丢进线段树里。每次查询的时候，我们只根据询问的[L,R]进行查询，若L>=l，则不会查询到l的贡献。若查询到了，则查询到的值一定是属于[L,i](也就是[L,R],此时枚举的i为R)的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e9
template<typename T>
void read(T&x){
    x=0;
    char ch=getchar();
    ll f=1;
    while(!isdigit(ch)){
        if(ch=='-')f*=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}
template<typename T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
//===========================================================
const int maxn=500000+100;
const int maxm=(1<<20)+100;
#define lson (rt<<1)
#define rson (rt<<1|1)
struct node{
    int l,r,val;
}tree[maxn<<2];
int flag;
void push_up(int rt){
    //if(flag)cerr<<tree[rt].val<<" "<<tree[rt].l<<" "<<tree[rt].r<<endl;
    tree[rt].val=min(tree[rson].val,tree[lson].val);
}
void build(int l,int r,int rt){
    tree[rt].l=l;tree[rt].r=r;
    if(l==r){
        tree[rt].val=inf;
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,lson);
    build(m+1,r,rson);
    push_up(rt);
}

void modify(int ql,int qr,int rt,int val){
    int l=tree[rt].l,r=tree[rt].r;
    if(ql<=l&&r<=qr){
        tree[rt].val=val;
        return ;
    }
    int m=(l+r)>>1;
    if(ql<=m)modify(ql,qr,lson,val);
    if(qr>m) modify(ql,qr,rson,val);
    push_up(rt);
}

int query(int ql,int qr,int rt){
    int l=tree[rt].l,r=tree[rt].r;
    if(ql<=l&&r<=qr){
        //cerr<<tree[rt].val<<" "<<tree[rt].l<<" "<<tree[rt].r<<endl;
        return tree[rt].val;
    }
    int res=inf;
    int m=(l+r)>>1;
    if(ql<=m)res=min(res,query(ql,qr,lson));
    if(qr>m)res=min(res,query(ql,qr,rson));
    push_up(rt);
    return res;
}
struct Q{
    int l,id;
    Q(int L,int I){
        l=L;
        id=I;
    }
};
vector<Q>que[maxn];
int n,q,a[maxn];
int ans[maxn];
int pre[maxm];

signed main(){
    //freopen("in.txt","r",stdin);
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)a[i]^=a[i-1];
    for(int i=1;i<=q;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        //cerr<<x<<" "<<y<<endl;
        que[y].push_back(Q(x,i));
        //que.push_back(Q(x,y,i));
    }
    build(1,n,1);
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=n;i++){
        pre[a[i-1]]=i;
        int L=pre[a[i]];
        if(~L)modify(L,L,1,i-L+1);
        for(auto x:que[i]){
            //cerr<<"yes"<<endl;
            ans[x.id]=query(x.l,i,1);
        }
    }
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]==inf?-1:ans[i]);
    }
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目12月24日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴