正解:线段树

解题报告:

题目大意是说给定一个数列,然后有若干次询问,每次询问一个区间内相同数字之间距离最近是多少$QwQ$.如果不存在相同数字输出-1就成$QwQ$

考虑先预处理出每个点的$pre$和$lst$,就前一个相同数字的位置和后一个相同数字的位置$QwQ$,然后在线段树上维护下每个点到达前一个相同数字的最短距离

然后对询问按左端点排序,每次查询右端点区间内的$min$就成,然后删去数的话就把它后一个数字的那个最短距离$update$成$inf$就成鸭$QwQ$

然后就做完了?$QwQ$(话说这个为什么是个黑昂,,,什么瞎评分昂_(:з」∠)_

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=5e5+;

int n,m,nxt[N],as[N],nw=,inf,tr[N<<];

struct node{int l,r,id;}nod[N];

map<int,int>M;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(node gd,node gs){return gd.l<gs.l;}

void modify(ri nw,ri l,ri r,ri to,ri dat)

{

    if(l==r)return void(tr[nw]=dat);

    ri mid=(l+r)>>;mid>=to?modify(nw<<,l,mid,to,dat):modify(nw<<|,mid+,r,to,dat);

    tr[nw]=min(tr[nw<<],tr[nw<<|]);

}

int query(ri nw,ri l,ri r,ri to_l,ri to_r)

{

    if(to_l<=l && r<=to_r)return tr[nw];

    ri mid=(l+r)>>,ret=inf;

    if(mid>=to_l)ret=query(nw<<,l,mid,to_l,to_r);

    if(mid<to_r)ret=min(ret,query(nw<<|,mid+,r,to_l,to_r));

    return ret;

}

int main()

{

//    freopen("522d.in","r",stdin);freopen("522d.out","w",stdout);

    n=read();m=read();memset(tr,,sizeof(tr));inf=tr[];

    rp(i,,n)

    {

        ri tmp=read();

        if(M[tmp])nxt[M[tmp]]=i,modify(,,n,i,i-M[tmp]);

        M[tmp]=i;

    }

    rp(i,,m)nod[i]=(node){read(),read(),i};sort(nod+,nod++m,cmp);

    rp(i,,m)

    {

        while(nw<nod[i].l){if(nxt[nw])modify(,,n,nxt[nw],inf);++nw;}

        as[nod[i].id]=query(,,n,,nod[i].r);

    }

    rp(i,,m)printf("%d\n",(as[i]==inf?-:as[i]));

    return ;

}

巴特西

$Codeforces\ 522D\ Closest\ Equals$ 线段树

正解:线段树

解题报告:

最新文章

热门文章