jzoj 5571 ffs

Description

费福斯是六兄弟中的老五，他喜欢老六塞克斯斯，他希望塞克斯斯高兴。所以他要帮塞克斯斯写作业。作业如下：
给一个1到n的排列p，一个子序列p[a,b]是好的当且仅当p_a,p_a+1...p_b排序之后是连续的整数。例如p={3,1,7,5,6,4,2}，其中p[3,6]排序之后是4,5,6,7，所以是好的。
对于一个子序列p[x,y]，请找出满足a≤x≤y≤b，p[a,b]是好的子序列，并且b-a最小的a和b。
提示：对于任意子序列p[x,y]，可以证明b-a最小的a和b是唯一的。

Input

第一行一个整数n，表

#include<bits/stdc++.h>
#define Mid (l+r>>1)
#define Ls no<<1,l,Mid
#define Rs no<<1|1,Mid+1,r
#define N 700007
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int Mi1[N],Ma1[N],a[N],Mi2[N],Ma2[N],pos[N];
bool operator == (const pii & A,const pii & B){
    return A.fi==B.fi&&A.se==B.se;
}
map<pii,pii> Map;
void build(int no,int l,int r) {
    if (l==r) {
        Mi1[no]=a[l]; Ma1[no]=a[r];
        Mi2[no]=pos[l]; Ma2[no]=pos[r];
        return;
    }
    build(Ls); build(Rs);
    Mi1[no]=Min(Mi1[no<<1],Mi1[no<<1|1]);
    Mi2[no]=Min(Mi2[no<<1],Mi2[no<<1|1]);
    Ma1[no]=Max(Ma1[no<<1],Ma1[no<<1|1]);
    Ma2[no]=Max(Ma2[no<<1],Ma2[no<<1|1]);
}
#define inf 1e9
int I1,I2,A1,A2,tot;
pii p[N];
#define sight(x) ('0'<=x&&x<='9')
template <class T>
inline void read(T &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('
'); }
inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
void quinit(){
    I1=inf; I2=inf; A1=-inf; A2=-inf;
}
void que(int no,int l,int r,int L,int R) {
    if (L<=l&&r<=R) {
        I1=Min(I1,Mi1[no]); I2=Min(I2,Mi2[no]);
        A1=Max(A1,Ma1[no]); A2=Max(A2,Ma2[no]); return;
    }
    if (L<=Mid) que(Ls,L,R);
    if (R> Mid) que(Rs,L,R);
}
int n,q,x,y,X,Y;
signed main () {
    freopen("5.in","r",stdin);
    freopen("ffs.out","w",stdout);
    read(n); 
    for (int i=1;i<=n;i++) read(a[i]),pos[a[i]]=i;
    build(1,1,n);
    read(q);
    while (q--) {
        read(x); read(y); p[tot=0]=pii(x,y);
        while (quinit(),que(1,1,n,x,y),A1-I1!=y-x) {
            if (Map.count(pii(x,y))) x=Map[pii(x,y)].fi,y=Map[pii(x,y)].se;
            X=I1,Y=A1,quinit(),que(1,1,n,X,Y);
            x=I2,y=A2;
            p[++tot]=pii(x,y);
        }
        writel(x),writeln(y);
        for (int i=0;i<tot;i++) Map[p[i]]=pii(x,y);
    } 
    return 0;
}

示排列长度。
第二行n个整数，表示排列p。
第三行一个整数q，表示询问组数。
接下来q行，每行两个整数x和y，表示一组询问。

Output

q行，每行两个整数a和b，表示答案。

Sample Input

10
2 1 4 3 5 6 7 10 8 9
5
2 3
3 7
4 7
4 8
7 8

Sample Output

Data Constraint

数据保证p是一个1到n的排列。

数据分为两个子任务。

子任务一：40分，保证n,q≤1000;

子任务二：60分，保证n,q≤100000。

Sol

code ：