http://www.51nod.com/Challenge/Problem.html#!#problemId=1571
题解
题目要求的最近点对不太符合区间加合性，所以不能直接用线段树在线做。
我们可以先把数据离散化，求出当前点左边离他最近的点的位置，从左到右扫一遍，更新当前点的距离，然后回答以当前点为右端点的查询，题目数据量很大必须快读快写，换行不能用priintf(" ")，只能用putchar(' ');不然会慢一倍然后T掉好几个数据。。。
1 #define dbg(x) cout<<#x<<" = "<< (x)<< endl 2 #define IO std::ios::sync_with_stdio(0); 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 using namespace std; 6 typedef long long ll; 7 typedef pair<ll,ll>P; 8 #define pb push_back 9 #define se second 10 #define fi first 11 #define rs o<<1|1 12 #define ls o<<1 13 #define inf 0x3f3f3f3f 14 const int N=5e5+5; 15 template <class T> 16 bool read(T &x){ 17 char c; 18 bool op = 0; 19 while(c = getchar(), c < '0' || c > '9') 20 if(c == '-') op = 1; 21 else if(c == EOF) return 0; 22 x = c - '0'; 23 while(c = getchar(), c >= '0' && c <= '9') 24 x = x * 10 + c - '0'; 25 if(op) x = -x; 26 return 1; 27 } 28 template <class T> 29 void write(T x){ 30 if(x < 0) putchar('-'), x = -x; 31 if(x >= 10) write(x / 10); 32 putchar('0' + x % 10); 33 } 34 int a[N],c[N]; 35 struct node{ 36 int l,r,id; 37 bool operator < (const node &t)const{ 38 return r<t.r; 39 } 40 }b[N]; 41 int minv[N*4]; 42 void push(int o){ 43 minv[o]=min(minv[ls],minv[rs]); 44 } 45 void build(int o,int l,int r){ 46 if(l==r){ 47 minv[o]=inf; 48 return; 49 } 50 int m=(l+r)>>1; 51 build(ls,l,m); 52 build(rs,m+1,r); 53 push(o); 54 } 55 void up(int o,int l,int r,int p,int v){ 56 if(l==r){ 57 minv[o]=min(minv[o],v); 58 return; 59 } 60 int m=(l+r)>>1; 61 if(p<=m)up(ls,l,m,p,v); 62 else up(rs,m+1,r,p,v); 63 push(o); 64 } 65 int qu(int o,int l,int r,int ql,int qr){ 66 if(l>=ql&&r<=qr){ 67 return minv[o]; 68 } 69 int m=(l+r)>>1; 70 int res=inf; 71 if(ql<=m)res=min(res,qu(ls,l,m,ql,qr)); 72 if(qr>m)res=min(res,qu(rs,m+1,r,ql,qr)); 73 return res; 74 } 75 int n,q; 76 int ans[N],le[N],last[N]; 77 int main(){ 78 read(n);read(q); 79 for(int i=1;i<=n;i++){ 80 read(c[i]); 81 a[i]=c[i]; 82 } 83 sort(c+1,c+1+n); 84 int n1=unique(c+1,c+1+n)-c-1; 85 for(int i=1;i<=n;i++){ 86 a[i]=lower_bound(c+1,c+1+n1,a[i])-c; 87 le[i]=last[a[i]]; 88 last[a[i]]=i; 89 } 90 for(int i=1;i<=q;i++){ 91 read(b[i].l);read(b[i].r); 92 b[i].id=i; 93 } 94 sort(b+1,b+1+q); 95 build(1,1,n); 96 for(int i=1,j=1;i<=n&&j<=q;i++){ 97 if(le[i]){ 98 up(1,1,n,le[i],i-le[i]); 99 } 100 while(j<=q&&b[j].r==i){ 101 ans[b[j].id]=qu(1,1,n,b[j].l,b[j].r); 102 j++; 103 } 104 } 105 for(int i=1;i<=q;i++){ 106 write(ans[i]<inf?ans[i]:-1); 107 putchar(' '); 108 } 109 }
代码借鉴自胡小兔巨佬