LibreOJ #6190. 序列查询（线段树+剪枝）

　　莫队貌似是过不了的，这题是我没见过的科技...

　　首先区间按右端点排序，然后一个扫描线，扫到某个区间右端点时候计算答案，线段树上节点的信息并不需要明确定义，我们只要求线段树做到当前扫到now时，查询[L,now]即为这一段的答案。

　　朴素的不加优化的做法，我们在每一个点R加进来的时候要更新1~R-1所有点，这样显然是会TLE的。

　　强调一遍我们只要求线段树做到当前扫到now时，查询[L,now]即为这一段的答案，因此我们记录一下更新到现在的最小的绝对值mn，对于线段树上每一节点都维护一个set，维护这个节点代表的区间里的数有序，每次新加进来一个数，我们直接查询他的前驱后继，算出绝对值后与mn比较，若是大于mn显然这个区间就不用更新了。为什么？再强调一遍线段树上节点的信息并不需要明确定义，我们只要求线段树做到当前扫到now时，查询[L,now]即为这一段的答案。

　　这样一个类似最优性剪枝之后的东西能保证复杂度吗？实际上是可以的。

　　至少在这题上，最坏的情况是一个这样的序列： 1 n n/2 n/4 n/8 n/16，也就是对于每一个位置顶多被递归到叶子logn次，也就是最坏复杂度$O(nlog^3n)$，但实际上是到不了这个复杂度的...也就可以过了

　　思考与扩展：这样一个东西可以用在离线处理一个区间某种信息的最值上

　　感谢栋栋的悉心教导我这样一个大傻逼QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<set>

#define ll long long

using namespace std;

const int maxn=,inf=;

struct poi{int l,r,pos;}q[maxn*];

int n,m,x,y,z,tot,mn;

int tree[maxn<<],a[maxn*],ans[maxn*];

set<int>s[maxn<<];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline int abs(int x){return x>=?x:-x;}

inline int min(int a,int b){return a>b?b:a;}

void build(int x,int l,int r)

{

    tree[x]=inf;if(l==r)return;

    int mid=(l+r)>>;

    build(x<<,l,mid);build(x<<|,mid+,r);

}

void update(int x,int l,int r,int cx,int delta)

{

    if(l==r){if(l==cx)return;tree[x]=min(tree[x],abs(a[l]-delta));mn=min(mn,tree[x]);return;}

    if(r<=cx)

    {

        set<int>::iterator it=s[x].lower_bound(delta);

        if((it==s[x].end()||abs(*it-delta)>=mn)&&(it==s[x].begin()||abs(*(--it)-delta)>=mn))

        {

            mn=min(mn,tree[x]);

            return;

        }

        int mid=(l+r)>>;

        update(x<<|,mid+,r,cx,delta);

        update(x<<,l,mid,cx,delta);

        tree[x]=min(tree[x<<],tree[x<<|]);

        return;

    }

    int mid=(l+r)>>;

    if(cx<=mid)update(x<<,l,mid,cx,delta);

    else update(x<<|,mid+,r,cx,delta),update(x<<,l,mid,cx,delta);

    tree[x]=min(tree[x<<],tree[x<<|]);

}

void pushset(int x,int l,int r,int cx,int delta)

{

    s[x].insert(delta);

    if(l==r)return;

    int mid=(l+r)>>;

    if(cx<=mid)pushset(x<<,l,mid,cx,delta);

    else pushset(x<<|,mid+,r,cx,delta);

}

int query(int x,int l,int r,int cl,int cr)

{

    if(cl<=l&&r<=cr)return tree[x];

    int mid=(l+r)>>,ret=inf;

    if(cl<=mid)ret=min(ret,query(x<<,l,mid,cl,cr));

    if(cr>mid)ret=min(ret,query(x<<|,mid+,r,cl,cr));

    return ret;

}

bool cmp(poi a,poi b){return a.r<b.r;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]);build(,,n);

    read(m);

    for(int i=;i<=m;i++)read(q[i].l),read(q[i].r),q[i].pos=i;

    sort(q+,q++m,cmp);

    for(int i=,j=;i<=m;i++)

    {

        for(;j<=q[i].r;j++)

        {

            mn=inf;

            update(,,n,j,a[j]);

            pushset(,,n,j,a[j]);

        }

        if(q[i].l==q[i].r)ans[q[i].pos]=inf;

        else ans[q[i].pos]=query(,,n,q[i].l,q[i].r-);

    }

    for(int i=;i<=m;i++)printf("%d\n",ans[i]);

    return ;

}