钦定 Y_1">X1>Y1X_1>Y_1，不难发现必须满足 Y_{max},\ X_{min}>Y_{min}">Xmax>Ymax, Xmin>YminX_{max}>Y_{max},\ X_{min}>Y_{min}， 再看特殊性质，不难发现直接递归求解即可，每次检查是否能达到当前的 XmaxX_{max} 或 YminY_{min}。 这里的 XmaxX_{max} 和 YminY_{min} 将原序列分成了两个部分，而两个部分正好是特殊性质，所以分两次递归即可。 代码： #include using namespace std; const int N=5e5+5; int n,m,q; int x[N],y[N],a[N],b[N],ta[N],tb[N]; int pma[N],pmi[N],pmb[N],pmj[N]; int sma[N],smi[N],smb[N],smj[N]; void init(){ pma[1]=pmi[1]=1; for(int i=2;ia[pma[i-1]]?i:pma[i-1]; } pmb[1]=pmj[1]=1; for(int i=2;ib[pmb[i-1]]?i:pmb[i-1]; } sma[n]=smi[n]=n; for(int i=n-1;i>=1;i--){ smi[i]=a[i]a[sma[i+1]]?i:sma[i+1]; } smb[m]=smj[m]=m; for(int i=m-1;i>=1;i--){ smj[i]=b[i]b[smb[i+1]]?i:smb[i+1]; } } bool chk1(int i,int j){ if(i==1||j==1) return 1; if(a[pmi[i-1]]a[pma[i-1]]) return chk1(i,pmb[j-1]); return 0; } bool chk2(int i,int j){ if(i==n||j==m) return 1; if(a[smi[i+1]]a[sma[i+1]]) return chk2(i,smb[j+1]); return 0; } bool sol(){ if(a[1]>=b[1]) return 0; init(); int ma=pma[n],mj=pmj[m]; if(a[pmi[n]]>=b[pmj[m]]||b[pmb[m]] `#include using namespace std; const int N=5e5+5; int n,m,q; int x[N],y[N],a[N],b[N],ta[N],tb[N]; int pma[N],pmi[N],pmb[N],pmj[N]; int sma[N],smi[N],smb[N],smj[N]; void init(){ pma[1]=pmi[1]=1; for(int i=2;i pmi[i]=a[i]a[pmi[i-1]]?i:pmi[i-1]; pma[i]=a[i]>a[pma[i-1]]?i:pma[i-1]; } pmb[1]=pmj[1]=1; for(int i=2;i pmj[i]=b[i]b[pmj[i-1]]?i:pmj[i-1]; pmb[i]=b[i]>b[pmb[i-1]]?i:pmb[i-1]; } sma[n]=smi[n]=n; for(int i=n-1;i>=1;i--){ smi[i]=a[i]a[smi[i+1]]?i:smi[i+1]; sma[i]=a[i]>a[sma[i+1]]?i:sma[i+1]; } smb[m]=smj[m]=m; for(int i=m-1;i>=1;i--){ smj[i]=b[i]b[smj[i+1]]?i:smj[i+1]; smb[i]=b[i]>b[smb[i+1]]?i:smb[i+1]; } } bool chk1(int i,int j){ if(i==1||j==1) return 1; if(a[pmi[i-1]]b[pmj[j-1]]) return chk1(pmi[i-1],j); if(b[pmb[j-1]]>a[pma[i-1]]) return chk1(i,pmb[j-1]); return 0; } bool chk2(int i,int j){ if(i==n||j==m) return 1; if(a[smi[i+1]]b[smj[j+1]]) return chk2(smi[i+1],j); if(b[smb[j+1]]>a[sma[i+1]]) return chk2(i,smb[j+1]); return 0; } bool sol(){ if(a[1]>=b[1]) return 0; init(); int ma=pma[n],mj=pmj[m]; if(a[pmi[n]]>=b[pmj[m]]||b[pmb[m]]a[pma[n]]) return 0; return chk1(pmi[n],pmb[m])&&chk2(pmi[n],pmb[m]); } int main(){ scanf("%*d%d%d%d",&n,&m,&q); for(int i=1;iscanf("%d",&x[i]); for(int i=1;iscanf("%d",&y[i]); for(int i=1;ita[i]=x[i]; for(int i=1;itb[i]=y[i]; for(int i=1;ia[i]=ta[i]; for(int i=1;ib[i]=tb[i]; bool res1=sol(); swap(n,m); for(int i=1;ia[i]=tb[i]; for(int i=1;ib[i]=ta[i]; bool res2=sol(); swap(n,m); putchar(res1||res2?'1':'0'); while(q--){ for(int i=1;ita[i]=x[i]; for(int i=1;itb[i]=y[i]; int kx,ky; scanf("%d%d",&kx,&ky); while(kx--){ int p,v; scanf("%d%d",&p,&v); ta[p]=v; } while(ky--){ int p,v; scanf("%d%d",&p,&v); tb[p]=v; } for(int i=1;ia[i]=ta[i]; for(int i=1;ib[i]=tb[i]; bool res1=sol(); swap(n,m); for(int i=1;ia[i]=tb[i]; for(int i=1;ib[i]=ta[i]; bool res2=sol(); swap(n,m); putchar(res1||res2?'1':'0'); } return 0; }`
P9870 [NOIP2023] 双序列拓展
笔记