题目链接
题面：
题意： 给定一个数组 ai，有m个询问，每个询问给定 l ，r 去区间 [ l , r ] 中相同的数字的最近距离。
题解： 考虑主席树。 当前是第 i 个数据，即 a [ i ] , 设 p [ a [ i ] ] 是 a [ i ] 之前离 a [ i ] 最近的相同的数的位置。 那么在第 i 棵树上的 p [ a [ i ] ] 位置 更新最小值为 a [ i ] - p [ a [ i ] ] 考虑查询 l ，r 我们在第 r 棵树上查询 l 以后的最小值。 因为本身就需要一个log的复杂度，那么就不离散化了，直接用map标记前一个数的位置。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #include<string> #include<queue> #include<bitset> #include<map> #include<unordered_map> #include<set> #define ui unsigned int #define ll long long #define llu unsigned ll #define ld long double #define pr make_pair #define pb push_back #define lc (cnt<<1) #define rc (cnt<<1|1) #define len(x) (t[(x)].r-t[(x)].l+1) #define tmid ((l+r)>>1) #define forhead(x) for(int i=head[(x)];i;i=nt[i]) #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define one(n) for(int i=1;i<=(n);i++) #define rone(n) for(int i=(n);i>=1;i--) #define fone(i,x,n) for(int i=(x);i<=(n);i++) #define frone(i,n,x) for(int i=(n);i>=(x);i--) #define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k)) #define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k)) #define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++) #define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++) #define cls(a) memset(a,0,sizeof(a)) #define cls1(a) memset(a,-1,sizeof(a)) #define clsmax(a) memset(a,0x3f,sizeof(a)) #define clsmin(a) memset(a,0x80,sizeof(a)) #define cln(a,num) memset(a,0,sizeof(a[0])*num) #define cln1(a,num) memset(a,-1,sizeof(a[0])*num) #define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num) #define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num) #define sc(x) scanf("%d",&x) #define sc2(x,y) scanf("%d%d",&x,&y) #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define scl(x) scanf("%lld",&x) #define scl2(x,y) scanf("%lld%lld",&x,&y) #define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z) #define scf(x) scanf("%lf",&x) #define scf2(x,y) scanf("%lf%lf",&x,&y) #define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z) #define scs(x) scanf("%s",x+1) #define scs0(x) scanf("%s",x) #define scline(x) scanf("%[^\n]%*c",x+1) #define scline0(x) scanf("%[^\n]%*c",x) #define pcc(x) putchar(x) #define pc(x) printf("%d\n",x) #define pc2(x,y) printf("%d %d\n",x,y) #define pc3(x,y,z) printf("%d %d %d\n",x,y,z) #define pck(x) printf("%d ",x) #define pcl(x) printf("%lld\n",x) #define pcl2(x,y) printf("%lld %lld\n",x,y) #define pcl3(x,y,z) printf("%lld %lld %d\n",x,y,z) #define pclk(x) printf("%lld ",x) #define pcf2(x) printf("%.2f\n",x) #define pcf6(x) printf("%.6f\n",x) #define pcf8(x) printf("%.8f\n",x) #define pcs(x) printf("%s\n",x+1) #define pcs0(x) printf("%s\n",x) #define pcline(x) for(int i=1;i<=15;i++) pcc(x);pcc('\n') using namespace std; const int inf=0x3f3f3f3f; const ll lnf=0x3f3f3f3f3f3f3f3f; const double dnf=1e18; const int mod=1e9+7; const double eps=1e-8; const double pi=acos(-1.0); const int maxm=100100; const int up=100000; const int hp=13331; const int maxn=500100; struct node { int cl,cr; int minn; }t[maxn*22]; int a[maxn],rt[maxn],cnt=0; map<int,int>mp; void init(void) { t[0].minn=inf; } int change(int now,int pos,int val,int l,int r) { int p=++cnt; t[p]=t[now]; t[p].minn=min(t[p].minn,val); if(l==r) return p; if(pos<=tmid) t[p].cl=change(t[now].cl,pos,val,l,tmid); else t[p].cr=change(t[now].cr,pos,val,tmid+1,r); return p; } int ask(int p,int pos,int l,int r) { if(l==r) return t[p].minn; int al=inf,ar=inf; if(pos<=tmid) al=ask(t[p].cl,pos,l,tmid),ar=t[t[p].cr].minn; else ar=ask(t[p].cr,pos,tmid+1,r); return min(al,ar);//min被宏定义掉了，直接取min会出问题（有可能会多次调用ask） } int main(void) { init(); int n,m; sc2(n,m); one(n) { sc(a[i]); rt[i]=rt[i-1]; if(mp.count(a[i])) rt[i]=change(rt[i-1],mp[a[i]],i-mp[a[i]],1,n); mp[a[i]]=i; } int l,r; one(m) { sc2(l,r); int now=ask(rt[r],l,1,n); pc(now==inf?-1:now); } return 0; }