题目概述

Equivalent Prefixes

解题报告

首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间（ $a_i$ 最小的区间），还有 $[LB_i,RB_i]$ 表示 $b_i$ 的控制区间。

那么对于 $i$ ，它能让 $[\max\{LA_i,LB_i\},i]$ 中的任何一个下标到 $[i,\min\{RA_i,RB_i\}]$ 中的任何一个下标所形成区间合法，这就是个经典的矩形覆盖问题。对于前 $i$ 个，如果 $\forall j\in[1,i]$ ，都有第 $j$ 列的 $[1,j]$ 全被覆盖了，说明前 $i$ 个是可行的。

因此扫描线+线段树就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000;

int n,a[2][maxn+5],L[2][maxn+5],R[2][maxn+5],top,stk[maxn+5];
struct data {int L,R,f;};vector<data> e[maxn+5];
int cnt[(maxn<<2)+5],ans;bool cov[(maxn<<2)+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Make(int ID){
    top=0;stk[0]=0;
    for (int i=1;i<=n;i++){
        while (top && a[ID][i]<a[ID][stk[top]]) top--;
        L[ID][i]=stk[top]+1;stk[++top]=i;
    }
    top=0;stk[0]=n+1;
    for (int i=n;i;i--){
        while (top && a[ID][i]<a[ID][stk[top]]) top--;
        R[ID][i]=stk[top]-1;stk[++top]=i;
    }
}
void Clear(int L,int R,int p=1){
    cnt[p]=cov[p]=0;if (L==R) return; int mid=L+(R-L>>1);
    Clear(L,mid,p<<1);Clear(mid+1,R,p<<1|1);
}
void Insert(int L,int R,int f,int l=1,int r=n,int p=1){
    if (L==l && r==R) {cnt[p]+=f;cov[p]=cnt[p]>0;return;} int mid=l+(r-l>>1);
    if (R<=mid) Insert(L,R,f,l,mid,p<<1); else if (L>mid) Insert(L,R,f,mid+1,r,p<<1|1);
    else Insert(L,mid,f,l,mid,p<<1),Insert(mid+1,R,f,mid+1,r,p<<1|1);
    cov[p]=cnt[p] || cov[p<<1] && cov[p<<1|1];
}
bool Ask(int L,int R,int l=1,int r=n,int p=1){
    if (cov[p]) return true;if (L==l && r==R) return false; int mid=l+(r-l>>1);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return Ask(L,mid,l,mid,p<<1) && Ask(mid+1,R,mid+1,r,p<<1|1);
}
int main(){
    freopen("H.in","r",stdin);freopen("H.out","w",stdout);
    while (~readi(n)){
        for (int i=1;i<=n;i++) readi(a[0][i]);
        for (int i=1;i<=n;i++) readi(a[1][i]);
        Make(0);Make(1);
        for (int i=1;i<=n+1;i++) e[i].clear();
        for (int i=1;i<=n;i++){
            int l=max(L[0][i],L[1][i]),r=i,A=i,B=min(R[0][i],R[1][i]);
            e[l].push_back((data){A,B,1});e[r+1].push_back((data){A,B,-1});
            e[A].push_back((data){l,r,1});e[B+1].push_back((data){l,r,-1});
        }
        Clear(1,n);
        for (int i=1;i<=n;i++){
            for (int si=e[i].size(),j=0;j<si;j++)
                Insert(e[i][j].L,e[i][j].R,e[i][j].f);
            if (Ask(1,i)) ans=i; else break;
        }
        printf("%d\n",ans);
    }
    return 0;
}