主席树14（区间内两数差的绝对值最小，主席树套树状数组）

CF765F Souvenirs

不得不说黑题实在太难搞了&＃xff0c;两天做一个题

由于这道题不强制在线&＃xff0c;所以可以离线处理

首先&＃xff0c;我们只考虑iajia_ji<j,ai​>aj​ 的情况&＃xff0c;然后在考虑ii<j,ai​<aj​的情况&＃xff0c;我们只需要数组取反即可&＃xff0c;我们先把问题离线&＃xff0c;将查询按右端点向左扫…

当我们右端点$r$的时候&＃xff0c;先找到$r$左边第一个$l$,满足al>ara_l>a_ral​>ar​&＃xff0c;用al−ara_l-a_ral​−ar​更新$l$左边的答案&＃xff0c;然后不断找到j左边&＃xff0c;比ala_lal​小&＃xff0c;比ara_rar​大的l′l&＃39;l′。

根据上述分析&＃xff0c;我们不难发现al′−aral′​−ar​<al​−al′​才可以更新答案&＃xff0c;移动不等式后发现2∗al′2∗al′​<al​&＃43;ar​&＃xff0c;所以每次更新后我们的$ans$都会减半&＃xff0c;那么我们的算法时间复杂度就变成了$log$了&＃xff0c;但是还是会超时,我们可以用树状数组进行优化&＃xff0c;更新答案的时候我们不再需要直接更新&＃xff0c;那时间复杂度就变成了nlogai&＃43;mloglogainloga_i&＃43;mlogloga_inlogai​&＃43;mloglogai​

这道题的主要思路就是在线转离线&＃xff0c;然后从右开始更新

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
#define inf 0x7fffffff
//#define ll long long
//#define int long long
//#define double long double
#define re int
#define void inline void
#define eps 1e-8
//#define mod 1e9&＃43;7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
using namespace std;
const int mod&＃61;998244353;
const int M&＃61;5e6;
const int N&＃61;3e6&＃43;5;//?????????? 4e8
struct node
{int l,r,sum;
}e[N*8];
int tot,rt[N];
int a[N],c[N],ans[N];
int n,m;
vector < P > q[N];
int p[N],cnt,ret[N],rk[N],s[N],st[N],top;
bool cmp(int x,int y){return a[x]<a[y];}
//bool cmp(const int &aa,const int &b) {return a[aa]
void insert(int &p,int pre,int l,int r,int pos)
{e[&＃43;&＃43;tot]&＃61;e[pre];p&＃61;tot;e[p].sum&＃43;&＃43;;if(l&＃61;&＃61;r) return;int mid&＃61;(l&＃43;r)>>1;if(pos<&＃61;mid) insert(e[p].l,e[pre].l,l,mid,pos);else insert(e[p].r,e[pre].r,mid&＃43;1,r,pos);
}
int ask(int L,int R,int l,int r,int pos)
{if(l&＃61;&＃61;r) return e[R].sum-e[L].sum;int mid&＃61;(l&＃43;r)>>1;if(pos<&＃61;mid) return ask(e[L].l,e[R].l,l,mid,pos);return ask(e[L].r,e[R].r,mid&＃43;1,r,pos)&＃43;e[e[R].l].sum-e[e[L].l].sum;
}
int find(int L,int R,int l,int r,int k)
{if(l&＃61;&＃61;r) return l;int mid&＃61;(l&＃43;r)>>1;int t&＃61;e[e[R].l].sum-e[e[L].l].sum;if(k<&＃61;t) return find(e[L].l,e[R].l,l,mid,k);return find(e[L].r,e[R].r,mid&＃43;1,r,k-t);
}
void update(int x,int val)
{for(re i&＃61;x;i;i-&＃61;i&-i) c[i]&＃61;min(c[i],val);
}
int query(int x)
{int mi&＃61;1<<30;for(re i&＃61;x;i<&＃61;n;i&＃43;&＃61;i&-i) mi&＃61;min(mi,c[i]);return mi;
}
void calc()
{re i;for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) p[i]&＃61;i;sort(p&＃43;1,p&＃43;n&＃43;1,cmp);for(cnt&＃61;0,i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(i&＃61;&＃61;1||a[p[i]]>a[p[i-1]]) ret[&＃43;&＃43;cnt]&＃61;a[p[i]];rk[p[i]]&＃61;cnt;}ret[0]&＃61;-1<<30,ret[cnt&＃43;1]&＃61;1<<30;tot&＃61;0;for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) insert(rt[rk[p[i]]],rt[rk[p[i-1]]],1,n,p[i]);memset(c,0x3f,sizeof(c));for(i&＃61;1,st[top&＃61;0]&＃61;0;i<&＃61;n;i&＃43;&＃43;){while(top&&rk[st[top]]<rk[i]) top--;int last&＃61;st[top];while(last){update(last,a[last]-a[i]);if(rk[i]&＃61;&＃61;rk[last]) break;int j&＃61;upper_bound(ret&＃43;1,ret&＃43;cnt&＃43;1,(a[last]&＃43;a[i])>>1)-ret-1;//if(ret[j]<a[i]) break;int t&＃61;ask(rt[rk[i]-1],rt[j],1,n,i);if(t&＃61;&＃61;1) break;last&＃61;find(rt[rk[i]-1],rt[j],1,n,t-1);}int sz&＃61;q[i].size();for(re j&＃61;0;j<sz;j&＃43;&＃43;) ans[q[i][j].second]&＃61;min(ans[q[i][j].second],query(q[i][j].first));st[&＃43;&＃43;top]&＃61;i;}
}
void solve()
{cin>>n;memset(ans,0x3f,sizeof(ans));for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&a[i]);cin>>m;for(re i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int l,r;scanf("%d%d",&l,&r);q[r].pb(mk(l,i));}calc();for(re i&＃61;1;i<&＃61;n;i&＃43;&＃43;) a[i]&＃61;-a[i];calc();for(re i&＃61;1;i<&＃61;m;i&＃43;&＃43;) printf("%d\n",ans[i]);
}
signed main()
{int T&＃61;1;
// cin>>T;for(int index&＃61;1;index<&＃61;T;index&＃43;&＃43;){solve();
// puts("");}return 0;
}
/*#((((#*/