CF765F Souvenirs 解题报告

CF765F Souvenirs

题意翻译

给出(n(2 le n le 10^5 )) ,一个长为(n)的序列(a(0 le a_i le 10^9 ))

给出(m(1le m le 2*10^5 )),接下来(m)组询问。

每组询问给出一个(l,r(1le l < rle n )),代表询问最小的(|a_i-a_j|) 的值((lle i <jle r)(a_i) 可以等于(a_j)


蒟蒻( t{Dew})又双叒叕花大几个小时去弄懂这个题,而直到现在,我也只是明白了这个题为什么可以这么做,却不是太明白这种题如何去想。


首先可以看出这个题说不定可以莫队套平衡树卡过去,没什么别的想法还是写写吧,估计比暴力还是强一些的。

然后考虑一些思考的出发点,比如

  • 值域?二分值域?划分修改?
  • 移动询问的指针?
  • 把询问给线段树分治掉?
  • 单调性?

不妨先考虑一些简单的暴力,比如说,我们把询问按右指针排序,然后开始处理它们。

若当前处理到的位置为(r),我们对(r)前面的位置(i)维护答案数组(ans_i),代表区间([i,r])的答案,每次移动右指针时,我们暴力更新每个位置的答案。

考虑修补这个暴力。

  • 发现询问(ans_i)也可以看做询问(min_{ile k <r} ans_k),这启发我们去区间查询,然后每次移动时不修改所有的值,选择线段树进行维护。
  • 具体的,在线段树上点代表的区间上,存下这个区间所有的(a_i),然后在这个区间上二分就能够更新这个区间的答案了。
  • 然后发现复杂度更高了,按道理有些值是不需要修改的,哪些值呢?
  • 发现(ans_i)数组是单调不升的。如果我们成功修改了位置靠右的某个值,并设当前的答案为(mi)(注意这个是包含原本节点的答案的最小值),那么在一个某个在(Ta)左边的节点上贡献的答案不如(mi)时,我们就没有必要进入这个节点的子节点了。
  • 这样做的复杂度单次操作是(log n log Maxa_i)的,原因其实很简单,每次成功贡献答案后答案必定减半。为什么?如果(r)(j)的答案为(mi_j)(r)(i)的答案为(mi_i),为了避免(i)直接把(j)给更新掉,一定有(mi_i< frac{mi_j}{2})

总结:积累做题经验,多开脑洞..


Code:

#include <cstdio>
#include <algorithm>
#include <vector>
const int N=1e5+10;
struct node
{
    int i,l,r;
    bool friend operator <(node n1,node n2){return n1.r<n2.r;}
}q[N<<2];
int ans[N<<2],Ans[N<<2],n,m,a[N],mi;
std::vector <int> seg[N<<2];
int min(int x,int y){return x<y?x:y;}
#define ls id<<1
#define rs id<<1|1
const int inf=0x3f3f3f3f;
void build(int id,int l,int r)
{
    for(int i=l;i<=r;i++) seg[id].push_back(a[i]);
    std::sort(seg[id].begin(),seg[id].end());
    ans[id]=inf;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
void change(int id,int l,int r,int p,int x)
{
    if(r<=p)
    {
        std::vector <int>::iterator it=std::upper_bound(seg[id].begin(),seg[id].end(),x);
        if(it!=seg[id].end()) ans[id]=min(ans[id],*it-x);
        if(it!=seg[id].begin()) ans[id]=min(ans[id],x-*(it-1));
        if(mi<=ans[id]) return;//右边已经有比Ta优秀的了
        if(l==r){mi=min(mi,ans[id]);return;}
    }
    int mid=l+r>>1;
    if(p>mid) change(rs,mid+1,r,p,x);//注意先走右边
    change(ls,l,mid,p,x);
    ans[id]=min(ans[id],min(ans[ls],ans[rs]));
    mi=min(mi,ans[id]);//最后更新Ta
}
int query(int id,int L,int R,int l,int r)
{
    if(L==l&&R==r) return ans[id];
    int Mid=L+R>>1;
    if(r<=Mid) return query(ls,L,Mid,l,r);
    else if(l>Mid) return query(rs,Mid+1,R,l,r);
    else return min(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].i=i;
    }
    std::sort(q+1,q+1+m);
    for(int p=1,i=2;i<=n;i++)
    {
        mi=inf;
        change(1,1,n,i-1,a[i]);
        for(;p<=m&&q[p].r<=i;++p)
            Ans[q[p].i]=query(1,1,n,q[p].l,i);
    }
    for(int i=1;i<=m;i++)
        printf("%d
",Ans[i]);
    return 0;
}

2018.11.29

原文地址:https://www.cnblogs.com/butterflydew/p/10040347.html