【CF765F】Souvenirs
题意：给你一个长度为n的序列{ai}，有m个询问，每次询问给出l,r，问在所有$l\le x < y\le r$中，$|a_x-a_y|$的最小值是多少。
$n\le 10^5,m\le 3\times 10^5,a_i\le 10^9$
题解：网上的标程都是在线段树上搞一搞就完事了，但是我怎么看都觉得是$O(n\log^3n)$的。看官方题解，里面也没写具体做法。于是我一脸懵逼的情况下用了主席树来维护，起码保证了$O(n\log^2n)$的复杂度。（应该是做麻烦了）
说做法吧。我们先只考虑$j<i,a_j>a_i$的情况，然后反过来再做一遍。首先比较暴力的思路就是先将询问离线，按右端点排序，然后枚举右端点。当我们扫到一个右端点i的时候，先找到i左边第一个比它大的数j，用$a_j-a_i$更新j左边的答案，然后不断找到j左边，比$a_j$小，比$a_i$大的j'，重复此步骤做下去。
而一个比较重要的性质就是我们找到的j'只有在满足$a_{j'}-a_i<a_j-a_{j'}$的情况下才是有意义的（否则就用$a_j-a_{j'}$做答案了），所以每次我们的差都会减半，所需次数为log次。如果用树状数组更新答案的话复杂度就是$O(n\log n\log a_i)$的了。
但是怎么找到下一个$j'$呢？我比较菜所以用的主席树。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n,m,N,top,pre,tot;
const int maxn=100010;
int v[maxn],st[maxn],sn[maxn],ans[maxn*3],p[maxn],rk[maxn],ref[maxn],rt[maxn];
struct node
{
int x,org;
node() {}
node(int a,int b) {x=a,org=b;}
};
vector<node> q[maxn];
vector<node>::iterator it;
int val[maxn<<2];
struct sag
{
int ls,rs,siz;
}s[maxn*20];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmp(const int &a,const int &b) {return v[a]<v[b];}
inline void updata(int x,int val)
{
for(int i=x;i;i-=i&-i) sn[i]=min(sn[i],val);
}
inline int query(int x)
{
int ret=1<<30;
for(int i=x;i<=n;i+=i&-i) ret=min(ret,sn[i]);
return ret;
}
inline void insert(int x,int &y,int l,int r,int a)
{
y=++tot,s[y].ls=s[x].ls,s[y].rs=s[x].rs,s[y].siz=s[x].siz+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(a<=mid) insert(s[x].ls,s[y].ls,l,mid,a);
else insert(s[x].rs,s[y].rs,mid+1,r,a);
}
inline int getrank(int x,int y,int l,int r,int a)
{
if(l==r) return s[y].siz-s[x].siz;
int mid=(l+r)>>1;
if(a<=mid) return getrank(s[x].ls,s[y].ls,l,mid,a);
return s[s[y].ls].siz-s[s[x].ls].siz+getrank(s[x].rs,s[y].rs,mid+1,r,a);
}
inline int find(int x,int y,int l,int r,int a)
{
if(l==r) return l;
int mid=(l+r)>>1,t=s[s[y].ls].siz-s[s[x].ls].siz;
if(a<=t) return find(s[x].ls,s[y].ls,l,mid,a);
return find(s[x].rs,s[y].rs,mid+1,r,a-t);
}
void work()
{
int i,j,t,last;
for(i=1;i<=n;i++) p[i]=i;
sort(p+1,p+n+1,cmp);
for(N=0,i=1;i<=n;i++)
{
if(i==1||v[p[i]]>v[p[i-1]]) ref[++N]=v[p[i]];
rk[p[i]]=N;
}
ref[0]=-1<<30,ref[N+1]=1<<30;
tot=0;
for(i=1;i<=n;i++) insert(rt[rk[p[i-1]]],rt[rk[p[i]]],1,n,p[i]);
memset(sn,0x3f,sizeof(sn));
for(st[top=0]=0,i=1;i<=n;i++)
{
while(top&&rk[st[top]]<rk[i]) top--;
last=st[top];
while(last)
{
updata(last,v[last]-v[i]);
if(rk[last]==rk[i]) break;
pre=0;
j=upper_bound(ref+1,ref+N+1,(v[last]+v[i])>>1)-ref-1;
if(ref[j]<v[i]) break;
t=getrank(rt[rk[i]-1],rt[j],1,n,i);
if(t==1) break;
last=find(rt[rk[i]-1],rt[j],1,n,t-1);
}
for(it=q[i].begin();it!=q[i].end();it++) ans[(*it).org]=min(ans[(*it).org],query((*it).x));
st[++top]=i;
}
}
int main()
{
n=rd();
int i,a,b;
for(i=1;i<=n;i++) v[i]=rd();
m=rd();
memset(ans,0x3f,sizeof(ans));
for(i=1;i<=m;i++) a=rd(),b=rd(),q[b].push_back(node(a,i));
work();
for(i=1;i<=n;i++) v[i]=-v[i];
work();
for(i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}//3 1 1 1 1 1 2