题解：CF2053C Bewitching Stargazer

· · 题解

赛时写了一个超级复杂的代码。

首先考虑直接暴力递归，但是这样的代码在最坏情况下是 O(n) 的，所以我们可以考虑一下优化。

当我们递归时，我们需要分别计算左区间和右区间，但是我们其实可以只算出来其中的一个区间，然后推出另外一个区间。

下面分 2 种情况考虑。

  1. 2 \mid len

设当前递归到的区间为 [l,r]。

我们记 cnt 为 [l,mid-1] 的答案，通过找规律可以发现，如果左区间有 num 个数被统计了答案，那么右区间的答案为 cnt+num(mid-l+1)。向上传回统计数时为 2num。

  1. 2 \nmid len

设当前递归到的区间为 [l,r]。

我们记 cnt 为 [l,mid-1] 的答案，通过找规律可以发现，如果左区间有 num 个数被统计了答案，那么右区间的答案为 cnt+num(mid-l+1)。向上传回统计数时为 2num+1。请注意这里是 2num+1，因为当前的 mid 也被统计了。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
int n,k;
pii dfs(int l,int r){
    int len=r-l+1;
    int mid=(l+r)>>1;
    int ans=0;
    int tmp=0;
    if (len&1){
        ans+=mid;
        int nlen=mid-l;
        if (nlen<k) return {ans,1};
        pii cnt=dfs(l,mid-1);
        ans+=cnt.fi*2+(nlen+1)*cnt.se;
        tmp+=1+cnt.se*2;
    }
    else{
        int nlen=mid-l+1;
        if (nlen<k) return {0,0};
        pii cnt=dfs(l,mid);
        ans+=cnt.fi*2+nlen*cnt.se;
        tmp+=cnt.se*2;
    }
    return {ans,tmp};
}
void sol(){
    cin>>n>>k;
    cout<<dfs(1,n).fi<<endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while (t--) sol();
    return 0;
}