企业官网建设流程全解析

加法入门

时间限制：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≦i<n; 1≦j≦i)ai,j​(1≦i<n;1≦j≦i)，若都有a i , j ≦ a i + 1 , j a_{i,j}≦a_{i+1,j}ai,j​≦ai+1,j​且a i , j ≦ a i + 1 , j + 1 a_{i,j}≦a_{i+1,j+1}ai,j​≦ai+1,j+1​，那么这座麻将塔是“平衡的”。

〖引用结束〗

在本题中，每一块麻将上的整数都各不相同，且为1 11到n × ( n + 1 ) 2 \frac{n×(n+1)}{2}2n×(n+1)​中的一个。A s k a l a n a AskalanaAskalana按整数从小到大的顺序，自上而下、自左而右的搭出了一座麻将塔。如下所示：

然而，就在A s k a l a n a AskalanaAskalana回房间休息的间隙，猫猫偷偷的将标注数字为l , l + 1 , … , r l,l+1,…,rl,l+1,…,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≦l<r≦\frac{n×(n+1)}{2})n,l,r(2≦n≦109;1≦l<r≦2n×(n+1)​)代表麻将塔的层数、翻转的区间。

输出描述：

对于每一组测试数据，新起一行。如果反转后的数组搭出的麻将塔是“平衡的”，输出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(n+1)}{2}2n(n+1)​按自然顺序自上而下、自左而右填入n nn层三角形塔。第i ii层有i ii个数字，数值范围是[ i ( i − 1 ) 2 + 1 , i ( i + 1 ) 2 ] \big[\frac{i(i-1)}{2}+1,\ \frac{i(i+1)}{2}\big][2i(i−1)​+1,2i(i+1)​]，层内严格递增。初始塔天然满足“平衡”要求（每个父节点数字不大于其左下、右下子节点数字）。
• 翻转操作：将区间[ l , r ] [l, r][l,r]内的值逆序映射，即x ↦ l + r − x x \mapsto l+r-xx↦l+r−x。问操作后全塔是否仍平衡。
• 跨层必然破坏：设l ll位于第L LL层。若r > L ( L + 1 ) 2 r > \frac{L(L+1)}{2}r>2L(L+1)​（区间延伸到下一层），则l ll的子节点必然落入[ l , r ] [l, r][l,r]内。翻转后l ll变成r rr，而子节点变为较小的值，导致父大于子，破坏平衡。
• 同层翻转无影响：若翻转区间完全包含在同一层内（r ≤ L ( L + 1 ) 2 r \le \frac{L(L+1)}{2}r≤2L(L+1)​），该层的父节点均来自上一层，其值严格小于该层最小值l ll，翻转后仍小于等于子节点；该层的子节点均位于下一层，其值严格大于该层最大值r rr，翻转后的父节点仍小于等于子节点。故平衡得以保持。
• 充要条件：翻转后仍平衡当且仅当区间不跨层，即区间长度len = r − l + 1 ≤ L \text{len}=r-l+1 \le Llen=r−l+1≤L（L LL为l ll所在层数）。

2. 算法实现：二分定位层数 + 条件判断

1. 预判：若len > n \text{len} > nlen>n，因层数L ≤ n L \le nL≤n，必定跨层，直接输出No。
2. 二分查找l ll所在层L LL：第k kk层末尾数字为k ( k + 1 ) / 2 k(k+1)/2k(k+1)/2。二分求最小的L LL满足L ( L + 1 ) / 2 ≥ l L(L+1)/2 \ge lL(L+1)/2≥l，即l ll的层号。
3. 结果判定：若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)判定。

代码简要说明

1. 主判断函数S()
   • 读取n , l , r n, l, rn,l,r；若len > n \text{len} > nlen>n直接输出no并返回。
   • 二分查找l ll的层数：初始L = 1 , R = 10 9 L=1, R=10^9L=1,R=109，计算m i d ( m i d + 1 ) / 2 mid(mid+1)/2mid(mid+1)/2与l ll比较，最终L LL即为l ll所在层。
   • 若len > L \text{len} > Llen>L输出no，否则输出yes。
2. 主函数：读入测试组数T TT，循环调用S()，使用快速 IO 提升效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll dx[4]={0,1,0,-1};ll dy[4]={1,0,-1,0};llqp(ll x,ll y){ll r=1;x%=mod;while(y){if(y&1)r=r*x%mod;x=x*x%mod;y>>=1;}returnr;}voidS(){ll n,l,r;cin>>n>>l>>r;if(r-l+1>n){cout<<"no\n";return;}ll L=1,R=1000000000;while(L<=R){ll mid=(L+R)>>1;ll num=mid*(mid+1)/2;if(l<=num)R=mid-1;elseL=mid+1;}if(r-l+1>L)cout<<"no\n";elsecout<<"yes\n";}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--)S();return0;}