题解 P4747 【[CERC2017]Intrinsic Interval】

ywy_c_asm · 2018-12-24 21:26:10 · 题解

这题真的是一道思维好题。（感谢i207M神犇提供的思路qwq）

首先显而易见的有这个好区间的max-min=r-l，不过要做这题光有这个还不够，做这种题的时候就不能把这堆数完全当做离散量来处理，我们还需要找出一些别的性质。

我们发现包含着这段区间的好区间可能会有很多吧，考虑两个包着这个区间的好区间[l_1,r_1]和[l_2,r_2]，我们只讨论不包含的情况（因为包含的话外层那个区间肯定是没用的），不妨设l_2>l_1，那么这两个区间的交[l_2,r_1]也是包含着这个询问区间的。既然他是两个好区间的交，我们不妨考虑这样一个问题：[l_2,r_1]为什么既能和[l_1,l_2-1]拼成一个好区间，又能和[r_1+1,r_2]拼成一个好区间？我们发现[l_2,r_1]居然也是一个好区间！假如他不好的话，也就是说中间不连续，那么它最多只能和一边的区间拼成好区间。那么我们可以断言，从r开始的第一个能够包住[l,r]的好区间的右端点对应的最短能够包住[l,r]的好区间就是唯一的答案（这话好绕口啊……）。

于是就可以有这样一个思路，我们维护一个扫描线，把这些区间离线下来，然后想办法找出当前点i对应的右端点的好区间按照l的顺序（用个set维护）直接处理掉。那么考虑如何找所有可行的左端点。

其实题面上已经给了我们一个非常好的提示：

若它的一个子串 \pi[a..b] 排序后是连续正整数，则称 \pi[a..b] 是一个“好区间”。

我们发现把这玩意排序之后相邻的两项差为1对吧，那么这个好区间[l,r]有多少无序二元组(i,j)是相邻两项或者绝对值为1呢？显然就是r-l，显然对于无序二元组可以在靠后的那个位置统计。那么我们就可以把好区间换个定义了：

在[l,r]内有r-l个无序二元组的区间

那么我们现在枚举的是r，那么直接找l后面有多少个二元组即可。于是我们可以把式子变形，不妨设val[l]为l后面有多少个合法的二元组，那么显然就有val[l]+l=r当且仅当[l,r]为好区间。于是我们就可以换一种角度进行统计：开一个初始值为下标的线段树，然后我们在扫描线的时候如果发现a_{i-1}或者a_{i+1}在i前面就把1~他们的位置进行区间加，显然值为i的位置就是可行的好区间。

那么我们该如何在处理询问的时候找出区间内等于i的最后一个位置呢？表面上看起来是不可做的，但是不难发现一个区间内最多只会有r-l个合法的二元组（其实就是把他们排序一下看然后就不可能再多了），也就是说等于i的位置是区间内的最大值，既然是最大值就可以在线段树上乱搞了。

上代码~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#define ls(_o) (_o<<1)
#define rs(_o) ((_o<<1)|1)
#define up(_o) maxn[_o]=max(maxn[ls(_o)],maxn[rs(_o)])
using namespace std;
namespace ywy{
    inline int get(){
        int n=0;char c;while((c=getchar())||23333){
            if(c>='0'&&c<='9')break;if(c=='-')goto s;
        }n=c-'0';while((c=getchar())||23333){
            if(c>='0'&&c<='9')n=n*10+c-'0';else return(n);
        }s:while((c=getchar())||23333){
            if(c>='0'&&c<='9')n=n*10-c+'0';else return(n);
        }
    }
    void print(int num){
        if(num>=10)print(num/10);putchar(num%10+'0');
    }
    int ansl[100001],ansr[100001];
    typedef struct _qj{
        int l;int r;int id;
        friend bool operator <(const _qj &a,const _qj &b){
            if(a.l==b.l)return(a.id<b.id);
            return(a.l<b.l);
        }
    }qj;
    set<qj> st;
    int ints[100001],pos[100001],maxn[1000001],adds[1000001];
    inline void down(int tree){
        if(!adds[tree])return;
        int cjr=adds[tree];
        adds[tree]=0;
        adds[ls(tree)]+=cjr;adds[rs(tree)]+=cjr;
        maxn[ls(tree)]+=cjr;maxn[rs(tree)]+=cjr;
    }
    int query(int rl,int rr,int l,int r,int tree,int num){//cout<<tree<<endl;
        down(tree);int mid=(l+r)>>1;
        if(rl>rr)return(-1);
        if(rl==l&&rr==r){
            if(maxn[tree]!=num)return(-1);if(l==r)return(l);
            if(maxn[rs(tree)]==num)return(query(mid+1,r,mid+1,r,rs(tree),num));
            return(query(l,mid,l,mid,ls(tree),num));
        }
        if(rl>mid)return(query(rl,rr,mid+1,r,rs(tree),num));
        if(rr<=mid)return(query(rl,rr,l,mid,ls(tree),num));
        int cjr=query(mid+1,rr,mid+1,r,rs(tree),num);
        if(cjr!=-1)return(cjr);
        return(query(rl,mid,l,mid,ls(tree),num));
    }
    vector<qj> vec[100001];
    void inc(int rl,int rr,int l,int r,int tree){
        if(rl==l&&rr==r){
            adds[tree]++;maxn[tree]++;return;
        }
        int mid=(l+r)>>1;down(tree);
        if(rl>mid)inc(rl,rr,mid+1,r,rs(tree));else{
            if(rr<=mid)inc(rl,rr,l,mid,ls(tree));else{
                inc(rl,mid,l,mid,ls(tree));
                inc(mid+1,rr,mid+1,r,rs(tree));
            }
        }up(tree);
    }
    void build(int l，int r,int tree){
        if(l==r){
            maxn[tree]=l;return;
        }
        int mid=(l+r)>>1;
        build(l,mid,ls(tree));
        build(mid+1,r,rs(tree));up(tree);
    }
    typedef set<qj>::iterator it;
    void ywymain(){
        int n=get();
        for(register int i=1;i<=n;i++)pos[ints[i]=get()]=i;
        int m=get();
        for(register int i=1;i<=m;i++){
            int l=get(),r=get();
            qj cjr;cjr.l=l;cjr.r=r;cjr.id=i;
            vec[r].push_back(cjr);
        }
        build(1,n,1);
        for(register int i=1;i<=n;i++){
            if(ints[i]!=1&&pos[ints[i]-1]<i)inc(1,pos[ints[i]-1],1,n,1);
            if(ints[i]!=n&&pos[ints[i]+1]<i)inc(1,pos[ints[i]+1],1,n,1);
            for(register int j=0;j<vec[i].size();j++){
                st.insert(vec[i][j]);
            }
            while(st.begin()!=st.end()){
                it lp=st.end();lp--;qj me=*lp;
                int cjr=query(1,me.l,1,n,1,i);
                if(cjr==-1)break;
                ansl[me.id]=cjr;
                ansr[me.id]=i;st.erase(lp);
            }
        }
        for(register int i=1;i<=m;i++)print(ansl[i]),putchar(' '),print(ansr[i]),putchar('\n')；
    }
}
int main(){
    ywy::ywymain();return(0);//再见程序
}