如何制作网站和网页,seo外链专员,如何开发wap网站,服务器多少钱蓝桥杯题型分类
二分
123
传送门 1. 小区间的构成
假设数列的构成是如下形式#xff1a;
第 1 个区间包含 1 个元素#xff08;1#xff09;。第 2 个区间包含 2 个元素#xff08;1 2#xff09;。第 3 个区间包含 3 个元素#xff08;1 2 3#xff09;。第 4 个区…蓝桥杯题型分类
二分
123
传送门 1. 小区间的构成
假设数列的构成是如下形式
第 1 个区间包含 1 个元素1。第 2 个区间包含 2 个元素1 2。第 3 个区间包含 3 个元素1 2 3。第 4 个区间包含 4 个元素1 2 3 4。…
第 i 个小区间包含 i 个元素。我们将这些小区间连起来形成整个数列。
2. 数组 a[j] 的定义
数组 a[j] 表示前 j 个小区间的总元素数同时也能表示每个小区间的和。例如
a[1] 1 表示前 1 个小区间有 1 个元素a[2] 1 2 3 表示前 2 个小区间共有 3 个元素a[3] 1 2 3 6 表示前 3 个小区间共有 6 个元素a[4] 1 2 3 4 10 表示前 4 个小区间共有 10 个元素
注意数组 a[j] 是单调递增的因为每个小区间的元素个数都在增加。
关键点k i - a[j]
数列中的位置 i 是在第 j1 个区间中的某个元素。前 j 个区间包含了 a[j] 个元素也就是说第 j1 个区间的第一个元素出现在位置 a[j] 1。
因此位置 i 在第 j1 个区间的具体位置是
第 j1 个区间的第 k 个元素k 就是位置 i 相对于第 j1 个区间开始位置的偏移量。
由于前 j 个区间包含了 a[j] 个元素第 j1 个区间从位置 a[j] 1 开始。所以位置 i 在第 j1 个区间中的具体位置是 k i - a[j] #include iostream
using namespace std;
using lllong long;
const int N1414215;ll a[N],s[N];ll persum(ll i)
{ll l0,rN;while(lr){ll mid(lr1)1;if(a[mid]i)lmid;else rmid-1;}return s[l]a[i-a[l]];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i1;iN;i){a[i]a[i-1]i;s[i]s[i-1]a[i];}int t;cint;while(t--){ll l,r;cinlr;coutpersum(r)-persum(l-1)endl;}return 0;
}
