题解：P4747 [CERC2017] Intrinsic Interval

· · 题解

真是一道美妙的思维好题

前言

今天高三学长给我们讲了这道题目，感觉十分巧妙，写一篇题解记录一下。

STEP 0

据说这道题有各种各样的高科技做法，比如说析合树、建图跑，但我通通不会。 这里讲一个非常震撼的小清新做法。（其实也是多数人写这道题的做法）

STEP 1

这种类型的区间要求看上去很不可做，所以我们先考虑把它离线下来，按照一定的扫描顺序去跑。但是具体怎么跑需要我们进一步对“好区间”的性质进行分析。

STEP 2

注意到！

两个好区间的交一定也是个好区间。

因为好区间的下标编号和值域连续的，所以作为连续的序列编号和连续的值域，它们的交也一定会是连续的。

注意到！！

一个区间 [l,r] 是好的的等价条件是 r-l=k ，其中 k 是连续数字对的个数。

这个等价条件其实是比较好理解的，但是没有逆天注意力谁能想到，，

当然，它还有一个等价条件是 \max-\min=r-l ，使用两种不同的条件都可以做出本题，不过实现起来似乎第一个条件更好用一些。

STEP 3

我们注意了这么多，总该考虑实现了吧。。

因为两个好区间的交也是好区间，所以如果有两个好区间 [l_1,r_1] ，[l_2,r_2]，且满足 l_1 \le l_2, r_1\le r_2 ,都包含了要询问的区间，那么它们都不可能成为答案，因为它们的交 [l_2,r_1] 是个长度更短且满足条件的好区间。所以我们只需要贪心的找右端点最靠左的可行区间就一定能找到答案。

于是我们以 r 为扫描线，并且开一颗线段树实施维护当前扫描到 r 时，对于每一个可能成为左端点的 i 的r-i-k 其中 k 是对应区间中的连续正整数对的个数。

初始时我们把线段树上每个点赋成 -i ，每扫描一个新的节点就把对应部分先区间加一，然后对于 r 产生的新的连续正整数对的贡献加上。具体实现中有一些细节，都在代码里了（有注释）

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int p[100005],ansl[100005],ansr[100005],id[100005];
struct que{
    int l,r,id;
    bool operator<(const que x)const{return l<x.l;}
}a[100005];
bool cmp(que a,que b){return a.r<b.r;}
struct node{int mn,laz,pos;}tr[100005<<2];
//一颗平平常常的记录最小值位置的线段树 
void pushup(int rt){
    tr[rt].mn=min(tr[lson].mn,tr[rson].mn);
    if(tr[rson].mn<=tr[lson].mn)tr[rt].pos=tr[rson].pos;
    else tr[rt].pos=tr[lson].pos;
}void pushdown(int rt){
    int k=tr[rt].laz;
    if(k){
        tr[lson].laz+=k,tr[lson].mn+=k;
        tr[rson].laz+=k,tr[rson].mn+=k;
        tr[rt].laz=0;
    }
}void update(int rt,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y)return tr[rt].laz+=k,tr[rt].mn+=k,void();
    int mid=l+r>>1;
    pushdown(rt);
    if(x<=mid)update(lson,l,mid,x,y,k);
    if(y>mid)update(rson,mid+1,r,x,y,k);
    pushup(rt);
}int query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[rt].mn==0?tr[rt].pos:-47;
    int ans=-47,mid=l+r>>1;
    pushdown(rt);
    if(x<=mid)ans=max(ans,query(lson,l,mid,x,y));
    if(y>mid)ans=max(ans,query(rson,mid+1,r,x,y));
    return ans;
}void build(int rt,int l,int r){
    tr[rt].laz=0;
    if(l==r)return tr[rt].mn=-l,tr[rt].pos=l,void();
    int mid=l+r>>1;
    build(lson,l,mid),build(rson,mid+1,r);
    pushup(rt);
}priority_queue<que>now;//因为每一次询问的答案的右端点不确定，所以我们要开一个以左端点为序的优先队列 
int main(){
    int n,m;scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&p[i]),id[p[i]]=i;//记录排列中每一种数字的出现位置 
    scanf("%d",&m);
    for(int i=1; i<=m; i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
    sort(a+1,a+1+m,cmp);
    int pos=1;
    build(1,1,n);
    for(int r=1; r<=n; r++){
        while(pos<=m&&a[pos].r<=r)now.push(a[pos++]);//把新产生的要处理的询问压到优先队列里 
        update(1,1,n,1,n,1);
        if(p[r]!=1&&id[p[r]-1]<r)update(1,1,n,1,id[p[r]-1],-1);
        if(p[r]!=n&&id[p[r]+1]<r)update(1,1,n,1,id[p[r]+1],-1);//对新产生的连续数对的贡献的计算 
        int tt=now.size();
        for(int i=0; i<tt; i++){
            que t=now.top();
            int as=query(1,1,n,1,t.l);
            if(as>0){//如果答案合法就记录 
                ansl[t.id]=as,ansr[t.id]=r;
                now.pop();
            }else{//否则就直接停掉，因为以左端点为序，所以合法性单调 
                break;
            }
        }
    }for(int i=1; i<=m; i++){
        printf("%d %d\n",ansl[i],ansr[i]);
    }
    return 0;
}//完结撒花 ^_^