题解 CF765F 【Souvenirs】
lhm_
2020-10-10 20:29:34
考虑将询问离线，固定右端点 $i$，这里只考虑满足 $j<i,a_j>a_i$ 的答案，因为将 $a_i$ 的值域翻转后再做一遍就能得到所有情况。询问就是查询对于每个位置 $j$ 得到的答案的后缀最小值。
用权值线段树就能找到满足 $j<i,a_j>a_i$ 的最大位置 $j$，但一个一个往前跳找出所有的位置 $j$，复杂度无法接受，还需进一步优化。
考虑当前位置为 $j$，要想下一次找到的位置 $j'$ 能更新答案，其必须满足 $a_{j'}-a_i<a_j-a_{j'}$，因为位置 $j'$ 更新过位置 $j$，要更新后缀最小值就必须满足这个式子。移项得 $a_{j'}-a_i<\frac{1}{2}(a_j-a_i)$，发现差值每次减半，设值域为 $V$，因此在限制下往前跳的合法位置个数为 $O(\log V)$。答案用树状数组维护后缀最小值即可。
复杂度为 $O(n \log^2 V)$。
```cpp
#include<bits/stdc++.h>
#define maxn 300010
#define maxm 10000010
#define all 1000000000
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,tot,root;
int a[maxn],ans[maxn],t[maxn],ls[maxm],rs[maxm],mx[maxm];
vector<pair<int,int> > ve[maxn];
void update(int x,int v)
{
while(x) t[x]=min(t[x],v),x-=lowbit(x);
}
int ask(int x)
{
int v=all;
while(x<=n) v=min(v,t[x]),x+=lowbit(x);
return v;
}
void modify(int l,int r,int pos,int v,int &cur)
{
if(!cur) cur=++tot;
mx[cur]=max(mx[cur],v);
if(l==r) return;
if(pos<=mid) modify(l,mid,pos,v,ls[cur]);
else modify(mid+1,r,pos,v,rs[cur]);
}
int query(int L,int R,int l,int r,int cur)
{
if(!cur) return 0;
if(L<=l&&R>=r) return mx[cur];
int v=0;
if(L<=mid) v=max(v,query(L,R,l,mid,ls[cur]));
if(R>mid) v=max(v,query(L,R,mid+1,r,rs[cur]));
return v;
}
void clear()
{
for(int i=1;i<=n;++i) t[i]=all;
for(int i=1;i<=tot;++i) ls[i]=rs[i]=mx[i]=0;
tot=root=0;
}
void work()
{
clear();
for(int i=1;i<=n;++i)
{
int pos=query(a[i],all,0,all,root);
while(pos)
{
update(pos,a[pos]-a[i]);
pos=query(a[i],(a[i]+a[pos])/2-(~(a[i]+a[pos])&1),0,all,root);
}
modify(0,all,a[i],i,root);
for(int j=0;j<ve[i].size();++j)
ans[ve[i][j].second]=min(ans[ve[i][j].second],ask(ve[i][j].first));
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i) read(a[i]);
read(m);
for(int i=1;i<=m;++i)
{
int l,r;
read(l),read(r),ans[i]=all;
ve[r].push_back({l,i});
}
work();
for(int i=1;i<=n;++i) a[i]=all-a[i];
work();
for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}
```