Souvenirs
题目大意
- 给出 \(n\) 以及一个长为 \(n\) 的序列 \(a\)。
- 给出 \(m\),接下来 \(m\) 组询问。
- 每组询问给出一个 \(l,r\),你需要求出,对于 \(i,j \in [l,r]\),且满足 \(i \neq j\),\(|a_i-a_j|\) 的最小值。
- \(1 \leq n \leq 10^5\),\(1 \leq m \leq 3\times 10^5\),\(0 \leq a_i \leq 10^9\)。
分析
给一个区间,让我们维护区间内值的差最小。第一眼看过去就是想能不能用主席树呢?但是权值又太大了,而且建起来之后,好像不能很好的让我们找到一个区间内的所有值的距离。但是这样划定一个范围,找区间内符合某些性质的点对,也是我们经常碰见的了。
我们考虑将询问离线,枚举右端点,这里我们只考虑\(j<i,a_j>a_i\)的答案,因为将\(a_i\)的值域反转后再做一遍就可以得到所有答案。我们维护的就是目标的值\(|a_j-a_i|\),然后求以当前右端点为结尾的询问,设该区间为[l,r]
,查询[1,l]
的后缀最小值。我们想计算右端点的贡献所有,那肯定可以去找所有的满足\(j<i,a_j>a_i\)。但是这时间复杂度我们是不可以接受的,我们要想办法优化。
考虑对于当前的位置\(j\),想让下一次找到的位置\(j'\)能更新答案,其必须满足\(a_{j'}-a_i<a_j-a_{j'}\),因为位置\(j'\)更新过位置\(j\),要更新后缀最小值,那就必须满足这个式子。移项后我们可以得到\(a_{j'}-a_i<\frac{1}{2}(a_j-a_i)\),也就是说新的位置\(j'\)必须的权值必须满足\(\frac{a_i+a_j}{2}<a_{j'}<a_i\)。这样每次我们查询的值都减半,设值域为\(V\),则时间复杂度为\(O(logV)\)。
还是满难想的。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 3e5 + 10,inf = 0x3f3f3f3f;
typedef pair<int,int> pii;
struct Node
{
int l,r;
int mx;
}tr[N*33];
int n,m,cnt,root;
int a[N],ans[N],t[N];
vector<pii> que[N];
void add(int x,int k)
{
while(x)
{
t[x] = min(t[x],k);
x -= x & -x;
}
}
int querymin(int x)
{
int res = inf;
while(x<=n)
{
res = min(res,t[x]);
x += x & -x;
}
return res;
}
void pushup(int u)
{
tr[u].mx = max(tr[tr[u].l].mx,tr[tr[u].r].mx);
}
void modify(int &u,int l,int r,int x,int k)
{
if(!u) u = ++cnt;
if(l==r)
{
tr[u].mx = max(tr[u].mx,k);
return ;
}
int mid = l + r >> 1;
if(x<=mid) modify(tr[u].l,l,mid,x,k);
else modify(tr[u].r,mid+1,r,x,k);
pushup(u);
}
int query(int u,int l,int r,int x,int y)
{
if(l>y||r<x) return 0;
if(!u) return 0;
if(x<=l&&r<=y) return tr[u].mx;
int mid = l + r >> 1;
return max(query(tr[u].l,l,mid,x,y),query(tr[u].r,mid+1,r,x,y));
}
void clear()
{
for(int i=1;i<=n;i++) t[i] = inf;
for(int i=1;i<=cnt;i++) tr[i].l = tr[i].r = tr[i].mx = 0;
root = cnt = 0;
}
void solve()
{
clear();
for(int i=1;i<=n;i++)
{
int pos = query(root,0,inf,a[i],inf);
while(pos)
{
add(pos,a[pos] - a[i]);
pos = query(root,0,inf,a[i],(a[i] + a[pos])/2 - (~(a[i]+a[pos])&1));
}
modify(root,0,inf,a[i],i);
for(auto it:que[i])
ans[it.second] = min(ans[it.second],querymin(it.first));
}
}
int main()
{
ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;cin>>l>>r;
ans[i] = inf;
que[r].push_back({l,i});
}
solve();
for(int i=1;i<=n;i++) a[i] = inf - a[i];
solve();
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}
标签:10,int,tr,Souvenirs,leq,inf
From: https://www.cnblogs.com/aitejiu/p/16882806.html