#C240218E. 区间加和

标签（Label）

思维
树状数组

网址（Website）

题目详情 - 区间加和 - Super

题解 - 区间加和 - Super

题解（Solution）

$\qquad$$10^6$的 $60pts$ 很好拿，只需要直接树状数组维护前缀和就好了。

$\qquad$对于后面的 $40pts$ ：由于此时的 $k$ 很大，因此我们想到了将所有要用到的数离散化，要用到的数就是询问、修改操作的每一个 $\ +1\ $ 所在的地方，即对于 $\ 1\ k\ $ 操作，原本我们需要在前缀数组里面将 $\ k+2,k+4,k+8,…\ $ 分别加 $\ 1$ ，这里就直接把这些地方存下来，排序后再去重。

$\qquad$去重之后对于每一个存下来的位置，要么是询问，要么是 $+$ ，而且 $+$ 项只会对比它更大的数字有效，因此直接用树状数组单点修改再加上前缀查询就好啦。o((>ω< ))o

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 6012345;

int n,ans=inf,cnt;
int a[N],c[N];

#define lbt(x) x&-x
inline void add(int x,int k){for(int i=x;i<=cnt;i+=lbt(i)) c[i]+=k;}
inline int ask(int x){int res=0;for(int i=x;i;i-=lbt(i)) res+=c[i];return res;}

int op[N],k[N];

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("sum");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	int Tim = clock(), T = input();
	For(i,1,T){
		cin>>op[i]>>k[i];
		a[++cnt]=k[i];//记得加询问的数字！！！ 
		if(op[i]==1){
			for(int j=1;k[i] + (1ll<<j) <= inf;j++)
				a[++cnt] = k[i] + (1ll<<j);
		}
	}
	a[++cnt]=inf;//这个地方要特别注意，防止lower_bound出问题 
	sort(a + 1,a + cnt + 1);
	cnt=unique(a + 1,a + cnt + 1) - a - 1;
	For(i,1,T){
		if(op[i]==1){
			for(int j=1;k[i] + (1ll<<j) <= inf;j++){
				int val = k[i] + (1ll<<j);
				int pos = lower_bound(a+1,a+cnt+1,val)-a;
				add(pos,1);
			}
		}else{
			int pos = lower_bound(a+1,a+cnt+1,k[i])-a;
			cout<<ask(pos)<<'\n';
		}
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}