线段树-思维好题-12.24考试-Intrinsic Interval-解题报告

· · 题解

今天考试正好考了这道题，然后我就因为读错题爆零了，回去钻研博客，发篇题解。

写在之前：这道题可以用图论的方法解决，具体思想是用线段树优化区间连边，然后缩scc...balabala

上面的我不会

我们把题干里描述的区间成为“好区间”。一条性质：好区间的交也是好区间。

处理这种问题，一个利器就是离线之后线段树扫描线。

设当前扫描线扫描到r，关键就是如何维护[l,r]是否为好的区间。

我先说方法，再说证明：

建立一棵线段树，维护最大值和最大值出现的最靠右的位置。设线段树上每个点的权值为val[i]，则初值为val[i]=i

从左到右扫描，设p[v]表示权值v出现的位置。执行下面的代码，其中upd为区间+1.

if(a[i]>1&&p[a[i]-1]<=i) upd(1,p[a[i]-1]);
if(a[i]<n&&p[a[i]+1]<=i) upd(1,p[a[i]+1]);

那么，如果val[l]==r，则[l,r]是“好区间”。

证明：

如果区间长度为2，即val[r-1]=r，那么显然a[r-1]=a[r]-1 \text{ or } a[r]+1

如果val[l]==r，那么val[l]处被++了r-l次。也就是说，在[l,r]区间内，存在r-l个相邻的数对。根据咕咕原理，权值区间一定是连续的。

换一种理解，如果[l,r]的权值区间为[c,d]+[e,f],e-d>1，那么d和e就不能贡献“相邻的数对”，所以val[l]被覆盖的次数一定<r-l次。

询问按L从大到小排序。

#define N 100005
#define M N*4
#define ls (x<<1)
#define rs (x<<1|1)
#define gm int mid((l+r)/2)
int n,a[N],p[N];
const int rt=1;
int mx[M],pos[M],laz[M];
il void up(int x)
{
    mx[x]=max(mx[ls],mx[rs]);
    pos[x]=mx[ls]>mx[rs]?pos[ls]:pos[rs];
}
il void down(int x)
{
    if(laz[x])
    {
        mx[x]+=laz[x];
        if(rs<M)
        {
            laz[ls]+=laz[x],laz[rs]+=laz[x];
        }
        laz[x]=0;
    }
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        mx[x]=pos[x]=l;
        return;
    }
    gm;
    build(ls,l,mid), build(rs,mid+1,r);
    up(x);
}
void upd(int x,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)
    {
        ++laz[x];
        down(x);
        return;
    }
    gm; down(x);
    if(ql<=mid) upd(ls,l,mid,ql,qr);
    else down(ls);
    if(qr>mid) upd(rs,mid+1,r,ql,qr);
    else down(rs);
    up(x);
}
int al,ar;
void ask(int x,int l,int r,int ql,int qr)
{
    down(x);
    if(ql<=l&&r<=qr)
    {
        if(mx[x]>=ar)
        {
            al=pos[x],ar=mx[x];
        }
        return;
    }
    gm;
    if(ql<=mid) ask(ls,l,mid,ql,qr);
    if(qr>mid) ask(rs,mid+1,r,ql,qr);
}
pairint ans[N];
bool judge(pairint x,int r)
{
    ar=-1; ask(rt,1,n,1,x.fi);
    if(ar==r)
    {
        ans[x.se]=mp(al,ar);
        return 1;
    }
    return 0;
}
vector<pairint>g[N];
priority_queue<pairint>s;
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
#endif
    in(n);
    for(ri i=1; i<=n; ++i) in(a[i]),p[a[i]]=i;
    int cntq; in(cntq);
    for(ri i=1,l,r; i<=cntq; ++i)
    {
        in(l),in(r);
        g[r].pb(mp(l,i));
    }
    build(rt,1,n);
    for(ri i=1; i<=n; ++i)
    {
        if(a[i]>1&&p[a[i]-1]<=i) upd(rt,1,n,1,p[a[i]-1]);
        if(a[i]<n&&p[a[i]+1]<=i) upd(rt,1,n,1,p[a[i]+1]);
        for(const pairint &v:g[i]) s.push(v);
        while(!s.empty())
        {
            if(judge(s.top(),i)) s.pop();
            else break;
        }
    }
    for(ri i=1; i<=cntq; ++i) out(ans[i].fi,' '),out(ans[i].se);
    return 0;
}