省流： (l+r)/2 与 (l+r)>>1 的区别

不省流：

MLE&TLE code:

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=200010,INF=1e9;
int n,q,dt,ans[N],a[N];
struct node{
	int x,y,k,typ,id;
}p[N+M],pl[N+M],pr[N+M];
inline int lowbit(int x){
	return x&(-x);
}
inline void add(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i))
		a[i]+=y;
}
inline int sum(int x){
	int dt1=0;
	for(int i=x;i>=1;i-=lowbit(i))
		dt1+=a[i];
	return dt1;
}
inline void solve(int p1,int p2,int l,int r){
//	cout<<"yyds"<<endl;
	if(p1>p2)
		return ;
	if(l==r){
//		cout<<l<<endl;
		for(int i=p1;i<=p2;i++)
			if(p[i].typ==2){
			ans[p[i].id]=l;
//			cout<<l<<endl;
		}				
		return ;
	}
	int mid=(l+r)/2,dt1=0,dt2=0;
	for(int i=p1;i<=p2;i++){
		if(p[i].typ==1){
			if(p[i].x<=mid){
				add(p[i].id,1);
				dt1++;
				pl[dt1]=p[i];
			}
			else{
				dt2++;
				pr[dt2]=p[i];
			}
		}
		else{
			int tot=sum(p[i].y)-sum(p[i].x-1);
			if(tot>=p[i].k){
				dt1++;
				pl[dt1]=p[i];
			}
			else{
				p[i].k-=tot;
				dt2++;
				pr[dt2]=p[i];
			}
		}
	}
	for(int i=1;i<=dt1;i++)
		if(pl[i].typ==1)
			add(pl[i].id,-1);
	for(int i=1;i<=dt1;i++)
		p[p1+i-1]=pl[i];
	for(int i=1;i<=dt2;i++)
		p[p1+dt1+i-1]=pr[i];
	solve(p1,p1+dt1-1,l,mid);
	solve(p1+dt1,p2,mid+1,r);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		dt++;
		p[dt]={x,1,INF,1,i};
	}
	for(int i=1;i<=q;i++){
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		dt++;
		p[dt]={x,y,k,2,i};
	}
	solve(1,dt,-INF,INF);
//	cout<<dt<<endl;
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;	
}

record

但是将第 34 行改为如下

	int mid=(l+r)>>1,dt1=0,dt2=0;

就过了

想知道为什么