加法入门时间限制1秒 空间限制1024M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述教会了猫猫数数Askalana决定教她一些更进一步的东西。本题与《B.数数入门》共享部分题目背景这一部分我们使用特殊的格式标注。〖引用开始〗A s k a l a n a AskalanaAskalana搭建了一个n nn层的麻将塔。从上往下数第i ii层由i ii块麻将组成。每一块麻将上面都刻了一个整数记第i ii层从左往右数第j jj块麻将上的数字为a i , j a_{i,j}ai,j。如下所示除最下层外每块麻将的左、右两角分别由其两块麻将支撑如果一座麻将塔中每一块麻将左下、右下支撑它的麻将上的整数均不小于它自身那么称这座麻将塔是“平衡的”。更具体地对于任意的a i , j ( 1 ≦ i n ; 1 ≦ j ≦ i ) a_{i,j}(1≦in; 1≦j≦i)ai,j(1≦in;1≦j≦i)若都有a i , j ≦ a i 1 , j a_{i,j}≦a_{i1,j}ai,j≦ai1,j且a i , j ≦ a i 1 , j 1 a_{i,j}≦a_{i1,j1}ai,j≦ai1,j1那么这座麻将塔是“平衡的”。〖引用结束〗在本题中每一块麻将上的整数都各不相同且为1 11到n × ( n 1 ) 2 \frac{n×(n1)}{2}2n×(n1)中的一个。A s k a l a n a AskalanaAskalana按整数从小到大的顺序自上而下、自左而右的搭出了一座麻将塔。如下所示然而就在A s k a l a n a AskalanaAskalana回房间休息的间隙猫猫偷偷的将标注数字为l , l 1 , … , r l,l1,…,rl,l1,…,r的麻将与标注数字为r , r − 1 , … , l r,r−1,…,lr,r−1,…,l的麻将互换了位置。Askalana 出来后看着被破坏的麻将塔突然想要知道现在的麻将塔还是“平衡的”吗输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 10 5 ) T(1≦T≦10^5)T(1≦T≦105)代表数据组数每组测试数据描述如下在一行上输入三个整数n , l , r ( 2 ≦ n ≦ 10 9 ; 1 ≦ l r ≦ n × ( n 1 ) 2 ) n,l,r(2≦n≦10^9; 1≦lr≦\frac{n×(n1)}{2})n,l,r(2≦n≦109;1≦lr≦2n×(n1))代表麻将塔的层数、翻转的区间。输出描述对于每一组测试数据新起一行。如果反转后的数组搭出的麻将塔是“平衡的”输出Y e s YesYes否则N o NoNo。您可以以任何大小写形式输出答案例如y E s yEsyEs、y e s yesyes和Y e S YeSYeS都将被视为肯定的回答。示例1输入3 5 1 15 5 2 3 5 2 4输出No Yes No说明对于第一组测试数据破坏后的麻将塔完全不平衡了。对于第二组测试数据我们使用橙色标注被破坏的位置得到的麻将塔如公式所示。解题思路本题利用三角形塔中数字的层结构特性将区间翻转后的平衡性判断转化为检测翻转区间是否跨层的简单条件。1. 问题等价转化初始塔结构数字1 11到n ( n 1 ) 2 \frac{n(n1)}{2}2n(n1)按自然顺序自上而下、自左而右填入n nn层三角形塔。第i ii层有i ii个数字数值范围是[ i ( i − 1 ) 2 1 , i ( i 1 ) 2 ] \big[\frac{i(i-1)}{2}1,\ \frac{i(i1)}{2}\big][2i(i−1)1,2i(i1)]层内严格递增。初始塔天然满足“平衡”要求每个父节点数字不大于其左下、右下子节点数字。翻转操作将区间[ l , r ] [l, r][l,r]内的值逆序映射即x ↦ l r − x x \mapsto lr-xx↦lr−x。问操作后全塔是否仍平衡。跨层必然破坏设l ll位于第L LL层。若r L ( L 1 ) 2 r \frac{L(L1)}{2}r2L(L1)区间延伸到下一层则l ll的子节点必然落入[ l , r ] [l, r][l,r]内。翻转后l ll变成r rr而子节点变为较小的值导致父大于子破坏平衡。同层翻转无影响若翻转区间完全包含在同一层内r ≤ L ( L 1 ) 2 r \le \frac{L(L1)}{2}r≤2L(L1)该层的父节点均来自上一层其值严格小于该层最小值l ll翻转后仍小于等于子节点该层的子节点均位于下一层其值严格大于该层最大值r rr翻转后的父节点仍小于等于子节点。故平衡得以保持。充要条件翻转后仍平衡当且仅当区间不跨层即区间长度len r − l 1 ≤ L \text{len}r-l1 \le Llenr−l1≤LL LL为l ll所在层数。2. 算法实现二分定位层数 条件判断预判若len n \text{len} nlenn因层数L ≤ n L \le nL≤n必定跨层直接输出No。二分查找l ll所在层L LL第k kk层末尾数字为k ( k 1 ) / 2 k(k1)/2k(k1)/2。二分求最小的L LL满足L ( L 1 ) / 2 ≥ l L(L1)/2 \ge lL(L1)/2≥l即l ll的层号。结果判定若len ≤ L \text{len} \le Llen≤L则输出Yes否则输出No。3. 复杂度分析时间复杂度每组数据O ( log n ) O(\log n)O(logn)二分查找总数据量T ≤ 10 5 T \le 10^5T≤105完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用常数变量。总结核心逻辑利用塔中数字按层连续递增的性质发现“平衡性不变”等价于“翻转区间完全位于同一层内”。通过二分定位l ll所在层并与区间长度比较即可O ( log n ) O(\log n)O(logn)判定。代码简要说明主判断函数S()读取n , l , r n, l, rn,l,r若len n \text{len} nlenn直接输出no并返回。二分查找l ll的层数初始L 1 , R 10 9 L1, R10^9L1,R109计算m i d ( m i d 1 ) / 2 mid(mid1)/2mid(mid1)/2与l ll比较最终L LL即为l ll所在层。若len L \text{len} LlenL输出no否则输出yes。主函数读入测试组数T TT循环调用S()使用快速 IO 提升效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dx[4]{0,1,0,-1};ll dy[4]{1,0,-1,0};llqp(ll x,ll y){ll r1;x%mod;while(y){if(y1)rr*x%mod;xx*x%mod;y1;}returnr;}voidS(){ll n,l,r;cinnlr;if(r-l1n){coutno\n;return;}ll L1,R1000000000;while(LR){ll mid(LR)1;ll nummid*(mid1)/2;if(lnum)Rmid-1;elseLmid1;}if(r-l1L)coutno\n;elsecoutyes\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;cinT;while(T--)S();return0;}
