题意:初始化数组a为[1,2...,n],对该区间进行反转操作后,对子区间[l,mid],[mid+1,r]中的元素个数大于2的区间进行同样的操作,直到最后所有子区间元素个数都为1,给出一个查找区间[l,r],求区间和
例如:[1,2,3,4,5]反转变为[5,4,3,2,1],第二次反转后为[3,4,5][1,2],第三次反转[4,3],[5],[1],[2],查询区间l=2,r=3,答案为8
Solution
来自小e的思路
对于题目来说,我们可以逆向思维,对查询区间进行反转操作,并且根据mid进行查询区间的拆分
注意当查询区间所在的区间长度为偶数时,mid=(l+r)/2会向下取整,在反转时要特别注意
在拆分查询区间时,如果反转次数为奇数,并且所在区间长度也为奇数,所以拆分的中间值应该是反过来的,例如[1,2,3,4,5]的拆分中间值是3,对于查询区间来说,一次反转后为[5,4,3,2,1]
1 int build(int L,int R,int l,int r,int cnt) 2 { 3 if(r<L||l>R||l>r||L>R)return 0; 4 if(L==l&&r==R) 5 { 6 return (r-l+1)*(l+r)/2; 7 } 8 int res=0; 9 int mid=(L+R)>>1; 10 if((R-L+1)&1) 11 { 12 l=2*mid-l,r=2*mid-r; 13 swap(l,r); 14 }else 15 { 16 l=2*mid-l+1,r=2*mid-r+1; 17 swap(l,r); 18 } 19 if((cnt&1)&&((R-L+1)&1)) 20 { 21 mid--; 22 } 23 res+=build(L,mid,max(L,l),min(mid,r),cnt+1); 24 res+=build(mid+1,R,max(l,mid+1),min(r,R),cnt+1); 25 return res; 26 } 27 28 29 void solve() 30 { 31 int n,l,r;cin>>n>>l>>r; 32 cout<<build(1,n,l,r,1); 33 }
标签:cnt,reverse,int,反转,mid,查询,区间,单题 From: https://www.cnblogs.com/HikariFears/p/17239881.html