HBC235686[SDOI2012]LONGGE的问题,数论可疑的区间题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

给出nnn个有趣的区间[L1,R1],[L2,R2],...,[Ln,Rn][L_1,R_1],[L_2,R_2],...,[L_n,R_n][L1,R1],[L2,R2],...,[Ln,Rn]，编号分别为1n1sim n1n，给出一个整数lenlenlen，对于任意一段长度为lenlenlen的区间[l,r],(rl+1=len)[l,r],(r-l+1=len)[l,r],(rl+1=l

给出 nnn 个有趣的区间 [L1,R1],[L2,R2],...,[Ln,Rn][L_1,R_1],[L_2,R_2],...,[L_n,R_n][L1​,R1​],[L2​,R2​],...,[Ln​,Rn​]，编号分别为 1∼n1sim n1∼n。给出一个整数 lenlenlen ，对于任意一段长度为 lenlenlen 的区间 [l,r],(r−l+1=len)[l,r],(r-l+1=len)[l,r],(r−l+1=len)，其中 lll 是正整数。其有趣值的定义为：与 [l,r][l,r][l,r] 有交集的有趣的区间个数。其权重的定义为：与 [l,r][l,r][l,r] 有交集的有趣的区间编号的总和。 例如有 333 个有趣的区间 [1,3],[2,4],[5,6][1,3],[2,4],[5,6][1,3],[2,4],[5,6]，编号分别为 1∼31sim 31∼3。 [2,3][2,3][2,3] 的有趣值为 222 ( [2,3][2,3][2,3] 与 [1,3],[2,4][1,3],[2,4][1,3],[2,4] 有交集)，权重为 1+2=31+2=31+2=3。 小宝选择了一段长度为 lenlenlen 的 [l,r],(r−l+1=len)[l,r],(r-l+1=len)[l,r],(r−l+1=len)，其中 lll 是正整数。小宝会选择有趣值最大的区间，如果两个区间有趣值相同，那么小宝会选权重最大的。 对于一段区间 [l,r],r−l+1=len[l,r],r-l+1=len[l,r],r−l+1=len ，其中 lll 是正整数。可能被小宝选择，那么这段区间就是可疑的，请输出可疑的区间的个数。

标签： HBC235686[SDOI2012]LONGGE的问题 数论可疑的区间题解