P8087 『JROI-5』Interval题目背景小 C 喜欢带有区间操作的数据结构因为这样的题总会有一档好写的O ( n 2 ) \mathcal{O}\left(n^2\right)O(n2)部分分。题目描述本题读入量较大建议使用较快的读入方式可以参考 赛时公告板小 C 有一个长度为n nn的序列a aa第i ii项为a i a_iai​。a aa是一个1 ∼ n 1\sim n1∼n的排列即1 ∼ n 1\sim n1∼n在a aa中各出现一次。定义Mex ⁡ l , r \operatorname{Mex}_{l,r}Mexl,r​为{ a l , a l 1 , ⋯ , a r − 1 , a r } \{a_l,a_{l1}, \cdots,a_{r-1},a_r\}{al​,al1​,⋯,ar−1​,ar​}中没有出现过的最小正整数。例如Mex ⁡ { 2 , 3 } 1 , Mex ⁡ { 1 , 2 , 3 } 4 \operatorname{Mex}\{2,3\}1,\operatorname{Mex}\{1,2,3\}4Mex{2,3}1,Mex{1,2,3}4。小 C 还有一个长度为n nn的数列f ff。定义一个区间[ l , r ] \left[l,r\right][l,r]是合法的当且仅当f r − l 1 Mex ⁡ l , r f_{r-l1} \operatorname{Mex}_{l,r}fr−l1​Mexl,r​小 C 希望你告诉他最短的合法区间的长度是多少特别的如果没有区间合法则输出0。输入格式第一行一个正整数n nn。第二行n nn个正整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1​,a2​,⋯,an​。第三行n nn个正整数f 1 , f 2 , ⋯ , f n f_1,f_2,\cdots,f_nf1​,f2​,⋯,fn​。输出格式一行一个整数表示最短的合法区间长度。输入输出样例 #1输入 #15 2 3 1 5 4 2 2 3 4 5输出 #13输入输出样例 #2输入 #25 2 3 1 5 4 1 2 2 4 5输出 #21输入输出样例 #3输入 #35 1 3 4 2 5 6 7 8 9 10输出 #30输入输出样例 #4输入 #4见附件输出 #4见附件说明/提示【样例解释】对于 #1容易发现[ 1 , 3 ] \left[1,3\right][1,3]是最短的合法区间。对于 #2容易发现[ 3 , 3 ] \left[3,3\right][3,3]是最短的合法区间。对于 #3容易发现没有合法的区间。对于10 % 10\%10%的数据满足1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤100。对于20 % 20\%20%的数据满足1 ≤ n ≤ 1000 1\leq n\leq 10001≤n≤1000。对于另外10 % 10\%10%的数据满足f ff不升即满足f 1 ≥ f 2 ≥ ⋯ ≥ f n f_1\geq f_2\geq\cdots\geq f_nf1​≥f2​≥⋯≥fn​且1 ≤ n ≤ 10 6 1\leq n\leq 10^61≤n≤106。对于100 % 100\%100%的数据满足1 ≤ n ≤ 4 × 10 6 , 1 ≤ f i ≤ 10 9 1\leq n\leq 4\times 10^6,1\leq f_i\leq 10^91≤n≤4×106,1≤fi​≤109。C实现#includebits/stdc.husingnamespacestd;intread(){intx0,fh1;charchgetchar();while(!isdigit(ch)){if(ch-)fh-1;chgetchar();}while(isdigit(ch)){x(x1)(x3)ch-0;chgetchar();}returnx*fh;}constintMAXN4e65;intf[MAXN],a[MAXN],n,pos[MAXN],qmin[MAXN],qmax[MAXN];intmain(){cinn;for(inti1;in;i)a[i]read(),pos[a[i]]i;for(inti1;in;i)f[i]read();qmin[0]2e9,qmax[0]-2e9;for(inti1;in;i)qmin[i]min(qmin[i-1],pos[i]),qmax[i]max(qmax[i-1],pos[i]);for(inti1;in;i){if(f[i]n)continue;intlqmin[f[i]],rqmax[f[i]];if(r-l1i){couti;return0;}}cout0;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容