题解 P5923 【[IOI2004]empodia 障碍段】

· · 题解

此题的关键在于对“数段”性质的使用。 考虑“数段”的性质：

1 起点为该数段最小的数字。

2 终点为该数段最大的数字且与起点不是同一个数字。

3 且介于这两个数字之间所有的整数都出现在这个数段中。

考虑“障碍段”的性质：

4 框段中并不包含更短的框段，则称之为障碍段

基本思路开个mp数组记录每一个数对应的位置，从后往前枚举区间起点，利用mp数组从起点开始跳。

如果跳到了一个点满足：

1 位置大于在这次过程中，之前跳到的所有点的位置

2 这个点的位置-起跳点的位置==这个点的数-起跳点的数

这就是个合法的数段。

我们考虑一下这个过程的复杂度，理论最劣可达到M^2;

考虑如何运用数段的性质优化这一过程。

如果我跳到了一个点在我的起跳点之前，考虑性质1，直接退出，必定不合法。

我们记录目前找到的区间的右端点位置，保留最小的那条记录R。考虑性质4，如果我跳的点的位置大于R，即使我这个区间满足性质123，也不能计入答案，故舍弃。

尽管如此，这个算法的复杂度还是没有保证，但实际上进行如此优化后速度很快，是目前的最优解（毕竟交的早）。

代码如下：

#include <bits/stdc++.h>
#define re register int 
#define il inline
#define ll long long
using namespace std;
const int inf=1e9;
il int read(){
    char c=getchar();int z=0,f=1;
    while(c!='-'&&(c>'9'||c<'0')) c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
    return z*f;
}
int R,n;
int mp[1100002],a[1100002];
int ans;
struct ANS{
    int x,y;
}q[1100002];
il void dfs(int l,int now,int r,int sum){
    if(r>=R) return ;
    if(mp[now]<l) return ;
    if(r==mp[now]&&sum>1&&sum==r-l+1) {
        q[++ans].x=l,q[ans].y=r,R=min(R,r);
        return ;
    }
    dfs(l,now+1,max(r,mp[now+1]),sum+1);
}
int main (){
    //Fuyuki是我们的红太阳 
    freopen("empodia.in","r",stdin);
    freopen("empodia.out","w",stdout);
    n=read();R=n+1;
    for(re i=1;i<=n;i++) a[i]=read(),mp[a[i]]=i;
    for(re i=n-2;i>=1;i--) 
        dfs(i,a[i],i,1);
    cout<<ans<<'\n';
    for(re i=ans;i>=1;i--)
        cout<<q[i].x<<' '<<q[i].y<<'\n';
    return 0;
}