原题链接

题意

在如题所示的二分代码流程中, r 的初始值可能大于 n. 那么通过 mid 访问的 a[mid] 就会越界. 统计有多少 $n\in [l,r]$ 满足越界次数不超过 k, 得到正确结果. ($l,r,k<=1e18$)

思路

第一个思路就是直接进行二分模拟, 但数据太大, 稳 tle 的. 但是思路对后面还是有用的, 我们看看:

这是一个类似二叉树的遍历, 最后会遍历到每一个 $n\in [l,r]$ 的.

int dfs(int l, int r, int k) {if (r < l || k < 0)return 0; // 二分结束if (r == l)return 1; // 当前区间长度为1, 最后一次二分, // 一定是不越界的, 这个位置是二分求的答案// 所以这个 n=l, 是合法答案.int mid = (r + l) / 2;return dfs(l, mid - 1, k - 1) + dfs(mid + 1, r, k) + 1;// 往左 => 执行了 r=mid-1; 说明 mid 是越界的. 所以 k-1// 往右 => 执行了 l=mid+1; 说明 mid 是不越界的. 所以 k 不变// n=mid 时, 这一次是不越界的, 故 +1,也是第一行临界条件 k<0 的由来.
}

考虑: 一个区间内合法的 n 的数量其实是和区间起点终点无关的, 只和区间长度有关, 故记忆化维护一下每个长度的答案. 大大优化时间. 每次二分只用走其中一半, 复杂度来到 log 级别.

代码:

#define int long long
map<int, map<int, int>>ma;
int dfs(int len, int k) {if (len <= 0 || k < 0)return 0;if (ma[len].count(k)) {return ma[len][k];}if (len == 1)return 1;int llen, rlen;if (len % 2 == 0){llen = len / 2 - 1;rlen = len / 2;}else{llen = len / 2;rlen = len / 2;}return ma[len][k] = dfs(llen, k - 1) + dfs(rlen, k) + 1;
}
int solve(int _) {int l, r, k;cin >> l >> r >> k;ma.clear();if (log2(r - l + 1) < k)return r - l + 1;return dfs(r - l + 1, k);
}