[CF765F]Souvenirs

题目大意：

给定一个长度为\(n(n\le2\times10^5)\)的数列\(A_{1\sim n}\)，\(m(m\le3\times10^5)\)次询问，每次询问区间\([l,r]\)内两个不相等的数之差的最小值。

思路：

将所有询问离线，按右端点排序。

枚举右端点\(r\)，用线段树维护对于当前的右端点，每个左端点对应的答案。

线段树每个结点维护对应区间归并排序后的状态，即构造一棵归并树。

插入新的右端点就相当于在线段树对应区间找到最接近的数，然后更新答案。

显然暴力更新的复杂度在最坏情况下是单次\(\mathcal O(n)\)的。

发现由于右端点固定，若左边的答案已经不会比右边优，则左端点已经没有更新的必要。先更新右子区间，再更新左子区间剪枝即可。

时间复杂度\(\mathcal O(m\log^2 n)\)。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=2e5+1,M=3e5;int a[N],ans[M],min;struct Query {    int l,r,id;    bool operator < (const Query &rhs) const {        return r
         
          >1 #define mid ((b+e)>>1) private: int val[N<<2]; std::vector
          
            v[N<<2]; public: void build(const int &p,const int &b,const int &e) { val[p]=INT_MAX; if(b==e) { v[p].push_back(a[b]); return; } build(p _left,b,mid); build(p _right,mid+1,e); v[p].resize(e-b+1); std::merge(v[p _left].begin(),v[p _left].end(),v[p _right].begin(),v[p _right].end(),v[p].begin()); } void modify(const int &p,const int &b,const int &e,const int &r,const int &x) { if(r==e) { auto it=std::lower_bound(v[p].begin(),v[p].end(),x); if(it
           
            =v[p].begin()) val[p]=std::min(val[p],std::abs(x-*it)); if(val[p]>=min) return; if(b==e) { min=val[p]; return; } } if(r>mid) modify(p _right,mid+1,e,r,x); modify(p _left,b,mid,std::min(mid,r),x); val[p]=std::min(val[p _left],val[p _right]); min=std::min(min,val[p]); } int query(const int &p,const int &b,const int &e,const int &l,const int &r) const { if(b==l&&e==r) return val[p]; int ret=INT_MAX; if(l<=mid) ret=std::min(ret,query(p _left,b,mid,l,std::min(mid,r))); if(r>mid) ret=std::min(ret,query(p _right,mid+1,e,std::max(mid+1,l),r)); return ret; } #undef _left #undef _right #undef _par #undef mid};SegmentTree t;int main() { const int n=getint(); for(register int i=1;i<=n;i++) a[i]=getint(); const int m=getint(); for(register int i=0;i