P11670 [USACO25JAN] Cow Checkups S题目描述Farmer John 的NNN1≤N≤5⋅1051 \leq N \leq 5 \cdot 10^51≤N≤5⋅105头奶牛站成一行奶牛111在队伍的最前面奶牛NNN在队伍的最后面。FJ 的奶牛也有许多不同的品种。他用从111到NNN的整数来表示每一品种。队伍从前到后第iii头奶牛的品种是aia_iai​1≤ai≤N1 \leq a_i \leq N1≤ai​≤N。FJ 正在带他的奶牛们去当地的奶牛医院进行体检。然而奶牛兽医非常挑剔仅愿意当队伍中第iii头奶牛为品种bib_ibi​1≤bi≤N1 \leq b_i \leq N1≤bi​≤N时对其进行体检。FJ 很懒惰不想完全重新排列他的奶牛。他将执行以下操作恰好一次。选择两个整数lll和rrr使得1≤l≤r≤N1 \leq l \le r \leq N1≤l≤r≤N。反转队伍中第lll头奶牛到第rrr头奶牛之间的奶牛的顺序。FJ 想要衡量这种方法有多少效果。求出对于所有N(N1)/2N(N1)/2N(N1)/2种可能的操作被兽医检查的奶牛数量之和。输入格式输入的第一行包含NNN。第二行包含a1,a2,…,aNa_1, a_2, \ldots, a_Na1​,a2​,…,aN​。第三行包含b1,b2,…,bNb_1, b_2, \ldots, b_Nb1​,b2​,…,bN​。输出格式输出一行包含对于所有可能的操作被兽医检查的奶牛数量之和。输入输出样例 #1输入 #13 1 3 2 3 2 1输出 #13输入输出样例 #2输入 #23 1 2 3 1 2 3输出 #212输入输出样例 #3输入 #37 1 3 2 2 1 3 2 3 2 2 1 2 3 1输出 #360说明/提示样例解释样例 #1如果 FJ 选择(l1,r1)(l1,r1)(l1,r1)(l2,r2)(l2,r2)(l2,r2)或(l3,r3)(l3,r3)(l3,r3)则没有奶牛将会被检查。注意这些操作并没有改变奶牛的位置。以下操作会导致一头奶牛被检查。(l1,r2)(l1,r2)(l1,r2)FJ 反转第一头和第二头奶牛的顺序因此新队伍中每头奶牛的品种将为[3,1,2][3,1,2][3,1,2]。第一头奶牛将会被检查。(l2,r3)(l2,r3)(l2,r3)FJ 反转第二头和第三头奶牛的顺序因此新队伍中每头奶牛的品种将为[1,2,3][1,2,3][1,2,3]。第二头奶牛将会被检查。(l1,r3)(l1,r3)(l1,r3)FJ 反转第一头第二头和第三头奶牛的顺序因此新队伍中每头奶牛的品种将为[2,3,1][2,3,1][2,3,1]。第三头奶牛将会被检查。所有六种操作中被检查的奶牛数量之和为000111300011130001113。样例 #2有三种导致333头奶牛被检查的可能操作(l1,r1)(l1,r1)(l1,r1)(l2,r2)(l2,r2)(l2,r2)和(l3,r3)(l3,r3)(l3,r3)。其余每种操作均导致111头奶牛被检查。所有六种操作中被检查的奶牛数量之和为333111123331111233311112。子任务测试点 4N≤100N\le 100N≤100。测试点 5N≤5000N\le 5000N≤5000。测试点 6-9aia_iai​bib_ibi​均在范围[1,N][1,N][1,N]内均匀随机生成。测试点 10-15aia_iai​bib_ibi​均在范围[1,2][1,2][1,2]内均匀随机生成。测试点 16-23没有额外限制。C实现#includebits/stdc.husingnamespacestd;intn,a[600000],b[600000],cnta[600000],cntb[600000],l,r;longlongans;intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d,a[i]);for(inti1;in;i)scanf(%d,b[i]);ln/21,rn/2;for(inti1;in;i)if(a[i]b[i])ansmin(i,n-i1)(1ll*i*(i-1)1ll*(n-i)*(n-i1))/2;for(inti1;i(n1)/2;i){//每次扩展往左往右都分别扩展一个长度if(rn)break;//防越界ans1ll*(cntb[a[r]]cnta[b[r]])*(n-r1);//a_r 和 b_r 做出的贡献cnta[a[r]],cntb[b[r]];//统计 a_r 和 b_r 出现的次数if(--l0)break;ans1ll*(cntb[a[l]]cnta[b[l]])*l;//向左扩展同理cnta[a[l]],cntb[b[l]];}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容