P10878 [JRKSJ R9] 在相思树下 III题目背景我知再迷恋他也非我能私有就当神爱世人遥远温柔未必要牵手隔千万光年宇宙献吻亦真切感受不用强求对号入座那虚构题目描述给你一个长为n nn的序列a 1 … n a_{1\dots n}a1…n​你需要对它进行两种操作共n − 1 n-1n−1次。对一个长度为l ll的序列b 1 … l b_{1\dots l}b1…l​进行一次操作将会把序列变为一个长为l − 1 l-1l−1的序列c 1 … l − 1 c_{1\dots l-1}c1…l−1​操作一中∀ i ∈ [ 1 , l ) , c i max ⁡ ( b i , b i 1 ) \forall i\in[1,l),c_i\max(b_i,b_{i1})∀i∈[1,l),ci​max(bi​,bi1​)操作二中∀ i ∈ [ 1 , l ) , c i min ⁡ ( b i , b i 1 ) \forall i\in[1,l),c_i\min(b_i,b_{i1})∀i∈[1,l),ci​min(bi​,bi1​)。给定整数m mm你只能进行至多m mm次操作一。进行n − 1 n-1n−1次操作后序列a aa的长度变为1 11。你可以任意安排操作的顺序求最终剩余的数a 1 a_1a1​的最大值。输入格式第一行两个整数n , m n,mn,m。第二行n nn个整数a i a_iai​表示初始序列。输出格式一个整数代表最终剩余的数的最大可能值。输入输出样例 #1输入 #14 2 1 2 3 3输出 #13说明/提示样例解释一种可能的操作顺序是进行一次操作一序列变为2 , 3 , 3 2,3,32,3,3进行一次操作二序列变为2 , 3 2,32,3进行一次操作一序列变为3 33。显然最终剩余的数不可能大于3 33。数据规模与约定本题采用捆绑测试。S u b t a s k \mathrm{Subtask}Subtaskn ≤ n\len≤特殊性质分数1 1110 101010 10102 225000 5000500030 30303 3310 6 10^6106✓ \checkmark✓20 20204 4410 6 10^610640 4040特殊性质保证∀ i ∈ [ 1 , n ] , a i ≤ 10 \forall i\in[1,n],a_i\le10∀i∈[1,n],ai​≤10。对于所有数据保证1 ≤ m n ≤ 10 6 1\leq m n \leq 10^61≤mn≤1061 ≤ a i ≤ 10 9 1 \leq a_i \leq 10^{9}1≤ai​≤109。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intn,m,ansLLONG_MAX;inta[1000005],b[1000005];structnode{intl,r,sum1;}tree[4000005];voidupd(intnow){tree[now].sum1max(tree[now1].sum1,tree[now1|1].sum1);}voidbuild(intnow,intl,intr){tree[now].ll;tree[now].rr;if(lr){tree[now].sum1a[l];return;}intmid(lr)1;build(now1,l,mid);build(now1|1,mid1,r);upd(now);}intsearch1(intnow,intl,intr){if(tree[now].lltree[now].rr)returntree[now].sum1;intmid(tree[now].ltree[now].r)1;if(rmid)returnsearch1(now1,l,r);elseif(lmid)returnsearch1(now1|1,l,r);elsereturnmax(search1(now1,l,mid),search1(now1|1,mid1,r));}signedmain(){scanf(%lld%lld,n,m);for(inti1;in;i){scanf(%lld,a[i]);}build(1,1,n);for(inti1;in-m;i){b[i]search1(1,i,im);ansmin(ans,b[i]);}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容