其实不用主席树

 

感觉像是离线问题

但是不能支持差分。分治又处理不了

考虑按照右端点排序，线段树维护左端点为i的时候的答案

然后trick一下，把求ansl，变成求min(ansl....ansr)，这样可以少更新很多

 

先把|ai-aj|变成j<i,aj>=ai这样找，然后再反过来做一次。

新加入的a[i]，找之前第一个大于a[i]的a[pos]，（pos是所在位置）

在pos位置更新答案。

对于k<pos，若a[k]>=a[pos],显然再和a[i]做贡献没有意义了。取到ansk一定能取到anspos

设mid=(a[pos]+a[i])/2，发现，对于k<pos，且a[k]>mid，a[k]和a[pos]做贡献一定更优（这在反过来的时候会考虑到），并且取到ansk一定能取到和pos做的贡献

所以只用考虑k<=mid，规模每次/2，log(max{ai})次logn

找pos，可以用动态开点线段树，每次找权值范围内最晚出现的。

 

复杂度：O(nlognlogai)

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=4e5+5;const int inf=0x3f3f3f3f;int n,m;int ans[N];int a[N];struct que{    int l,r,id;}q[N];bool cmp1(que a,que b){    return a.r
          
           b.l;}#define mid ((l+r)>>1)namespace tr1{int rt;struct node{ int ls,rs; int tim; node(){ tim=0; }}t[N*40];int tot;void pushup(int x){ t[x].tim=max(t[t[x].ls].tim,t[t[x].rs].tim);}int fin(int x,int l,int r,int L,int R){ if(L>R) return 0; if(!x) return 0; if(L<=l&&r<=R){ if(l==r) return t[x].tim; if(t[t[x].ls].tim>t[t[x].rs].tim) return fin(t[x].ls,l,mid,L,R); else return fin(t[x].rs,mid+1,r,L,R); } if(R<=mid) return fin(t[x].ls,l,mid,L,R); if(L>mid) return fin(t[x].rs,mid+1,r,L,R); return max(fin(t[x].ls,l,mid,L,R),fin(t[x].rs,mid+1,r,L,R));}void chan(int &x,int l,int r,int p,int ti){ if(!x) x=++tot; if(l==r){ t[x].tim=max(t[x].tim,ti);return; } if(p<=mid) chan(t[x].ls,l,mid,p,ti); else chan(t[x].rs,mid+1,r,p,ti); pushup(x);}void init(){ t[0].tim=0; tot=0;}void clear(){ for(reg i=1;i<=tot;++i){ t[i].ls=t[i].rs=0; t[i].tim=0; } tot=0;rt=0;}}namespace tr2{#define ls (x<<1)#define rs (x<<1|1)int ans[4*N];void build(int x,int l,int r){ if(l==r){ ans[x]=inf;return ; } ans[x]=inf; build(x<<1,l,mid);build(x<<1|1,mid+1,r);}void pushup(int x){ ans[x]=min(ans[ls],ans[rs]);}void upda(int x,int l,int r,int p,int c){ if(l==r){ ans[x]=min(ans[x],c);return; } if(p<=mid) upda(ls,l,mid,p,c); else upda(rs,mid+1,r,p,c); pushup(x);}int query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R) return ans[x]; if(R<=mid) return query(ls,l,mid,L,R); if(L>mid) return query(rs,mid+1,r,L,R); return min(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));}void clear(){ memset(ans,0x3f,sizeof ans);}}int main(){// cout<<" 23333 "<
           
            =1;--i){ if(i!=n){ int pos=tr1::fin(tr1::rt,0,lim,a[i],lim); while(pos){ pos=n-pos+1; tr2::upda(1,1,n,pos,a[pos]-a[i]); pos=tr1::fin(tr1::rt,0,lim,a[i],min(a[pos]-1,(a[pos]+a[i])/2)); } } while(ptr<=m&&q[ptr].l==i){ ans[q[ptr].id]=min(ans[q[ptr].id],tr2::query(1,1,n,i,q[ptr].r)); ++ptr; } tr1::chan(tr1::rt,0,lim,a[i],n-i+1); }// cout<<" turn2 "<