题面

实验室里有n种细胞，它们被排成了一行，从左往右编号1到n。我们可以用细胞分裂剂使一段区间的细胞分裂成两倍。
例如，对于这一行细胞 {1 2 3 3 4 5}, 我们在区间[2,5]使用分裂剂后就变成了 {1 2 2 3 3 3 3 4 4 5}.
在经过若干次操作后，请你找出指定区间中，哪种细胞的数量最多。  
第一行，两个整数n和m分别表示细胞的种数和操作的数量。 (1 <= n,m<= 50000)
解下来m行，每行描述一个操作。有两种操作：
Q l r，询问区间[l,r]的，数量最多的哪种细胞的个数
D l r, 使用分裂剂将区间[l,r]的细胞分裂成两倍


0 <= r – l <= 10^8, 1 <= l, r <= 细胞的数量

My code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+100;
int tree_sum[MAXN],tree_max[MAXN],tag[MAXN],a[MAXN];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void push_up(int p){
	tree_sum[p]=tree_sum[ls(p)]+tree_sum[rs(p)];
	tree_max[p]=max(tree_max[ls(p)],tree_max[rs(p)]);
}
void chan(int p,int pl,int pr){
	if(pl==pr){
		tree_max[p]=tree_max[p]=a[pl];
		return ;
	}
	int mid=(pl+pr)>>1;
	chan(ls(p),pl,mid);
	chan(rs(p),mid+1,pr);
	push_up(p);
}
void build(int p,int pl,int pr){
	if(pl==pr){
		tree_sum[p]=tree_max[p]=a[pl];
		return ;
	}
	tag[p]=0;
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}
void addtag(int p,int pl,int pr,int d){
	tag[p]+=d;
	tree_sum[p]=tree_sum[p]*pow(2,d);
	if(pl==pr) tree_max[p]=tree_sum[p];
}
void push_down(int p,int pl,int pr){
	if(tag[p]){
		int mid=(pl+pr)>>1;
		addtag(ls(p),pl,mid,tag[p]);
		addtag(rs(p),mid+1,pr,tag[p]);
		tag[p]=0;
	}
}
void update(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R){
		addtag(p,pl,pr,1);
		return ;
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(L<=mid) update(L,R,ls(p),pl,mid);
	if(R>mid) update(L,R,rs(p),mid+1,pr);
	push_up(p);
}
int find_k(int p,int pl,int pr,int k){
	if(pl==pr){
		return pl;
	}
	int mid=(pl+pr)>>1;
	if(tree_sum[ls(p)]>=k) return find_k(ls(p),pl,mid,k);
	else return find_k(rs(p),mid+1,pr,k-tree_sum[ls(p)]);
}
int query_sum(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R){
		return tree_sum[p];
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1,res=0;
	if(L<=mid) res+=query_sum(L,R,ls(p),pl,mid);
	if(R>mid) res+=query_sum(L,R,rs(p),mid+1,pr);
	return res;
}
int query_max(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R) return tree_max[p];
	int mid=(pl+pr)>>1,res;
	if(L<=mid) res=query_max(L,R,ls(p),pl,mid);
	if(R>mid) res=max(res,query_max(L,R,rs(p),mid+1,pr));
	return res;
}
int main(){
	int n,q;scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) a[i]=1;
	build(1,1,n);
	while(q--){
		char op;cin>>op;
		int x,y;scanf("%d%d",&x,&y);
		if(op=='D'){
			int _left=find_k(1,1,n,x);
			int _right=find_k(1,1,n,y);
			if(_left+1<=_right-1) update(_left+1,_right-1,1,1,n);
			int leftsum;
			if(_left==1) leftsum=0;
			else leftsum=query_sum(1,_left-1,1,1,n);
			int rightsum;
			if(_right==1) rightsum=0;
			else rightsum=query_sum(1,_right-1,1,1,n);
			a[_left]+=a[_left]-(x-leftsum-1);
			if(_left!=_right) a[_right]+=y-rightsum;
			chan(1,1,n);
		}
		else{
			int _left=find_k(1,1,n,x);
			int _right=find_k(1,1,n,y);
			int ans=query_max(_left,_right,1,1,n);
			printf("%d\n",ans);
		}
	}
	return 0;
}