牛客练习赛53 E-老瞎眼pk小鲜肉（思维+线段树+离线）

前言

听说是线段树离线查询？？

做题做着做着慢慢对离线操作有点感觉了，不过也还没参透，等再做些题目再来讨论离线、在线操作。

这题赛后看代码发现有人用的树状数组，$tql$。当然能用树状数组写的线段树也能写，最重要的还是思维上面。

我当时是怎么想来着。一看异或和前缀和不是很像么，我先把数组中所有数字连续异或并存起来，就像处理前缀和一样的。之后对于每组查询，我只要找到区间中相等的数就可以了，然后再取这些数中相隔最近的距离输出即可。想法很好，但是现实很骨感，这样一来每个区间都这样处理不就超时了么，遂放弃。

题意

给出一段长度为$n$的区间，$q$次询问求$L\sim R$这个区间内最短的一段区间$l\sim r$使得$\oplus_{i=l}^{r} a_j= 0$其中$L\leq l<r\leq r$

分析

首先预处理出对于每个位置$i$找到左边离$i$最近的位置$j$使得$a[j] \wedge a[j+1] \wedge a[j+2]\wedge …a[i]=0$，并记作$pre[i]$。

将询问按$r$从小到大排序，然后从$1\sim n$处理每个位置，对于位置$i$，在线段树上$pre[i]$更新为$i-pre[i]+1$（$i$与离$i$右边最近满足$\oplus_{i=l}^{r} a_j= 0$的$r$间的距离），然后查询$(Q[i].l, Q[i].r)$的最小值即可　$[link]$

Code

#include <cstdio>

#include <algorithm>

#define lson rt<<1, l , mid

#define rson rt<<1|1, mid+1 , r

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 5e5+6;

int n, q;

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

struct node{

    int l,r,id;

    bool operator<(const node x)const{

        return r<x.r;

    }

}Q[maxn];

void push_up(int rt){

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

}

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

    if(l==r){

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

        return;

    }

    int mid = (l+r)>>1;

    if(pos<=mid) update(lson, pos, val);

    else update(rson, pos, val);

    push_up(rt);

}

int query(int rt, int l, int r, int ul, int ur){

    if(ul<=l&&r<=ur) return tree[rt];

    int mid = (l+r)>>1, ans = INF;

    if(ur<=mid) return query(lson, ul, ur);

    else if(ul>mid) return query(rson, ul, ur);

    else return min(query(lson, ul, ur),query(rson, ul, ur));

}

/*这种写法也可以，但是就我以前做过的一道题目来说上面那种更快(不知道为啥，还有待考证)

int query(int rt, int l, int r, int ul, int ur){

    if(ul<=l&&r<=ur) return tree[rt];

    int mid = (l+r)>>1, ans = INF;

    if(ul<=mid) ans = min(ans, query(lson, ul, ur));

    if(ur>mid) ans = min(ans, query(rson, ul, ur));

    return ans;

}

*/

int main(){

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

    for(int i = 1;i <= 4*500000; i++){

        pos[i] = -1;

        tree[i] = INF;

    }

    int sum = 0; pos[0] = 0;

    for(int i = 1,x; i <= n; i++){

        scanf("%d",&x);

        sum ^= x;

        if(pos[sum]!=-1) pre[i] = pos[sum]+1;

        else pre[i] = -1;

        pos[sum] = i;

    }

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

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

        Q[i].id = i;

    }

    sort(Q+1, Q+1+q);

    int cnt = 1;

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

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

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

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

            cnt++;

        }

    }

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

        printf("%d\n", ans[i]==INF?-1:ans[i]);

    }

    return 0;

}

思考

说实话现在也只是知道了这题这么做是对的，但是自己很难会想到这个方法，可能要多做些题目才知道吧，据说和HH的项链很像，有时间就去看下这题。

还有就是我看这题代码的时候有个想法就是，能不能把$update(1, 1, n, pre[i], i-pre[i]+1)$换成$update(1, 1, n, i, i-pre[i]+1)$。当时觉得这样应该是差不多的，然而$WA$。

仔细想想后，发现用$pre[i]$的位置记录线段长度是有原因的，并非$pre[i]$和$i$都可以。如果用$pre[i]$也即是左端点记录线段长度的话，对于每组查询而言，区间内每个满足条件的点，它所代表的线段的右端点都不会超过当前的$r$，因此可以用来直接求最小值。但是！！假如是用$i$也即是右端点来记录线段长度的话，区间内每个满足条件的点，它所代表的线段的左端点都可能会超过当前的$l$，那个点就不能用来求最小值，但很显然计算的时候会把这个点计入，所以这样得到的结果可能就是错的！！

参考博客：

https://www.cnblogs.com/zjl192628928/p/11661714.html

巴特西

牛客练习赛53 E-老瞎眼pk小鲜肉（思维+线段树+离线）

最新文章

热门文章