题意
以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
| void build(int id,int l,int r){
value[id]+=r-l+1;
if(l==r) return;
int mid=(r+l)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
return;
}
long long run(int n,int x){
for(int i=1;i<=n;++i) build(1,1,i);
return(value[x]);
}
|
给出 组询问 ，问 run(n,x) 的返回值。
思路
找规律。
我们对于同一个 与不同的 进行打表。
然后可以发现首先是若干个 0，然后是一个递增序列（废话）。
对这个递增序列（包括第一项的 0）进行差分，然后发现这个差分很有规律。
具体的，规律如下：
- 若 是偶数：
- 前 项为 1。
- 之后为公差为 1 的等差序列，然后将其中每个数重复 次。
- 若 是奇数：
- 公差为 1 的等差序列，然后将其中每个数重复 次。
然后考虑计算 0 的个数，可以二分，然后构造到 的路径。
之后计算是十分简单的。
CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=1000010,FSIZE=1<<26;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
for(;48>*InF||*InF>57;++InF);
for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
int st[N];
ll f(ll r,ll x){
ll re=1;
for(;x;x>>=1) st[++st[0]]=x&1;
for(;r>1&&--st[0];)
if(st[st[0]]){
re=re<<1|1;
r>>=1;
}else{
re<<=1;
r=(r+1)>>1;
}
st[0]=0;
return(re);
}
ll find_zero(ll x){
ll l=1,r=x,mid;
for(;l<r;)
if(f(mid=(l+r)>>1,x)!=x) l=mid+1;
else r=mid;
return(r);
}
void work(){
ll n,x,b,ans=0;
read(n);read(x);
b=1ull<<(63-__builtin_clzll(x));
n-=find_zero(x)-1;
if(n<=0){
printf("0\n");
return;
}
if(!(x&1)){
n+=b>>1;
ans-=b>>1;
}
ans+=(((n/b+1)*(n/b))>>1)*b+n%b*(n/b+1);
printf("%lld\n",ans);
}
int main(){
fread(BuF,1,FSIZE,stdin);
int t;
for(read(t);t--;work());
fclose(stdin);
fclose(stdout);
return(0);
}
|